三个字符串的LCS(最长公共子序列)  


难度级别
经常问 亚马逊 编码国家 Expedia的 谷歌 尤伯杯 百会
动态编程

问题“三个字符串的最长公共子序列”表示给您3个字符串。 找出这3个字符串中最长的公共子序列。 LCS是在3个字符串中通用的字符串,并且由在所有3个给定字符串中具有相同顺序的字符组成。

使用案列  

三个字符串的LCS(最长公共子序列)Pin

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

途径  

问题给了我们3个字符串作为输入,并要求他们从中找出最长的公共子序列。 子序列是当我们从原始字符串中删除某些字符时剩下的字符串。 因此,我们需要在给定的3个字符串中找到具有最大长度的公共子序列。

该问题的幼稚方法与正常的最长公共子序列问题非常相似。 我们已经讨论了LongestCommon子序列问题。 但是,我们还讨论了幼稚的方法不足以在时限内解决问题。 因此,在不超过时间限制的情况下解决问题。 我们将使用 动态编程 解决问题。 该条件将类似于2个字符串的LCS。 在这里,我们将有3个状态,它们将引用3个相应字符串中的索引。 因此,我们的dp数组将是一个3D数组,如果其中0个索引中的任何一个索引为3,我们将在其中存储0。如果所有3个索引中的字符均为1,那么我们将为子问题的答案(来自子字符串的LCS)添加0。长度小于每个索引的1到XNUMX)。 如果两个字符串中的任何一个都不具有相同的字符,则我们将最大的子问题存储在索引中,每个子问题将索引中的每一个递减。

参见
数组中范围的乘积

代码  

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(最长公共子序列)具有多项式空间复杂度。