세 문자열의 LCS (Longest Common Subsequence)


난이도 하드
자주 묻는 질문 아마존 CodeNation Expedia 구글 동네 짱 조호 (Zoho)
동적 프로그래밍

“3 개 문자열의 LCS (Longest Common Subsequence)”문제는 3 개의 문자열이 주어 졌다는 것을 나타냅니다. 이 3 개 문자열의 가장 긴 공통 하위 시퀀스를 찾으십시오. LCS는 3 개의 문자열에서 공통적 인 문자열로 주어진 XNUMX 개의 문자열 모두에서 동일한 순서를 갖는 문자로 구성됩니다.

세 문자열의 LCS (Longest Common Subsequence)

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

접근

이 문제는 3 개의 문자열을 입력으로 제공하고이 중에서 가장 긴 공통 하위 시퀀스를 찾도록 요청했습니다. 하위 시퀀스는 원래 문자열에서 일부 문자를 삭제할 때 남는 문자열입니다. 따라서 우리는 최대 길이를 가진 주어진 3 개의 문자열에서 공통 하위 시퀀스를 찾아야합니다.

문제에 대한 순진한 접근 방식은 일반적인 Longest Common Subsequence 문제의 접근 방식과 매우 유사합니다. 우리는 이미 LongestCommon Subsequence 문제에 대해 논의했습니다. 그러나 우리는 또한 순진한 접근 방식이 시간 제한 아래에서 문제를 해결하기에 충분히 효율적이지 않다고 논의했습니다. 따라서 제한 시간을 초과하지 않고 문제를 해결합니다. 우리는 사용할 것입니다 동적 프로그래밍 질문을 해결하기 위해. 조건은 2 개 문자열에 대한 LCS의 조건과 유사합니다. 여기에는 3 개의 해당 문자열에있는 인덱스를 참조하는 3 개의 상태가 있습니다. 따라서 우리의 dp 배열은 3D 배열이 될 것입니다. 여기서 0 개의 인덱스 중 하나가 3이면 0을 저장합니다. 3 개의 인덱스에서 문자가 모두 있으면 하위 문제에 대한 답에 1을 더합니다 (아래의 하위 문자열의 LCS). 길이는 각 인덱스보다 0에서 1 작음). 두 문자열 중 하나가 동일한 문자를 가지고 있지 않으면 각 인덱스를 하나씩 감소시키는 하위 문제의 최대 값을 저장합니다.

암호

3 개 문자열의 LCS를 찾는 C ++ 코드

#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

3 개 문자열의 LCS를 찾기위한 Java 코드

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, M의 메이크업 시연, 그리고 한국에서 사랑을 담아 보낸 K. 사용하기 때문에 동적 프로그래밍 지수 시간 복잡도를 다항식으로 줄일 수 있습니다.

공간 복잡성

O (N * M * K), 더 작은 하위 문제에 대한 결과를 저장하고 그 결과를 결합하여 초기 문제에 대한 답을 얻기 위해 3D DP 배열을 만들어야하기 때문입니다. 따라서 세 문자열의 LCS (Longest Common Subsequence)를 찾는 것은 다항식 공간 복잡도를 갖습니다.