三個字符串的LCS(最長公共子序列)


難度級別
經常問 亞馬遜 編碼國家 Expedia的 谷歌 尤伯杯 百會
動態編程

問題“三個字符串的最長公共子序列”表示給您3個字符串。 找出這3個字符串中最長的公共子序列。 LCS是在3個字符串中通用的字符串,並且由在所有3個給定字符串中具有相同順序的字符組成。

三個字符串的LCS(最長公共子序列)

"gxtxayb" 
"abgtab" 
"gyaytahjb"
Length of LCS: 4("gtab")

途徑

問題給了我們3個字符串作為輸入,並要求他們從中找出最長的公共子序列。 子序列是當我們從原始字符串中刪除某些字符時剩下的字符串。 因此,我們需要在給定的3個字符串中找到具有最大長度的公共子序列。

該問題的幼稚方法與正常的最長公共子序列問題非常相似。 我們已經討論了LongestCommon子序列問題。 但是,我們還討論了幼稚的方法不足以在時限內解決問題。 因此,在不超過時間限制的情況下解決問題。 我們將使用 動態編程 解決問題。 該條件將類似於2個字符串的LCS。 在這裡,我們將有3個狀態,它們將引用3個相應字符串中的索引。 因此,我們的dp數組將是一個3D數組,如果其中0個索引中的任何一個索引為3,我們將在其中存儲0。如果所有3個索引中的字符均為1,那麼我們將為子問題(從長度小於每個索引的0到1)。 如果兩個字符串中的任何一個都不具有相同的字符,則我們將最大的子問題存儲在索引中,每個子問題將索引中的每一個遞減。

推薦碼

C ++代碼查找3個字符串的LCS

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  string x = "gxtxayb"; 
  string y = "abgtab"; 
  string z = "gyaytahjb"; 
  int n = x.length(), m = y.length(), l = z.length();
  
  int dp[n][m][l];
  memset(dp, 0, sizeof dp);
  for (int i=0; i<n; i++){ 
    for (int j=0; j<m; j++){ 
      for (int k=0; k<l; k++){
        if (x[i] == y[j] && x[i] == z[k])
          dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
        else
          dp[i][j][k] = max({i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0, k>0 ? dp[i][j][k-1] : 0}); 
      } 
    } 
  } 
  cout<<dp[n-1][m-1][l-1];
  return 0; 
}
4

Java代碼查找3個字符串的LCS

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String x = "gxtxayb"; 
    String y = "abgtab"; 
    String z = "gyaytahjb"; 
    int n = x.length(), m = y.length(), l = z.length();
    
    int dp[][][] = new int[n][m][l];
    for (int i=0; i<n; i++){ 
      for (int j=0; j<m; j++){ 
        for (int k=0; k<l; k++){
          dp[i][j][k] = 0;
          if (x.charAt(i) == y.charAt(j) && x.charAt(i) == z.charAt(k))
            dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
          else
            dp[i][j][k] = Math.max(Math.max(i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0), k>0 ? dp[i][j][k-1] : 0); 
        } 
      } 
    } 
    System.out.println(dp[n-1][m-1][l-1]);
  }
}
4

複雜度分析

時間複雜度

O(N * M * K), 因為我們必須遍歷具有長度的所有3個字符串 N, MK。 由於使用 動態編程 我們能夠將指數時間複雜度降低為多項式。

空間複雜度

O(N * M * K), 因為我們必須創建一個3D DP數組來存儲較小子問題的結果,然後組合結果以獲得初始問題的答案。 因此,找到三個字符串的LCS(最長公共子序列)具有多項式空間複雜度。