Shortest Common Supersequence

HardStringDynamic Programming

문제 설명

주어진 두 문자열 str1str2를 모두 부분 문자열(subsequence)로 가지고 있는 최단 문자열을 반환합니다.

  • 유효한 문자열이 여러 개 있으면, 그 중 하나를 반환합니다.
  • 문자열 t 에서 일부 문자를 삭제하면 문자열 s 가 생성되는 경우 문자열 s는 문자열 t부분 문자열(subsequence)입니다.

문제 풀이

Longest Common Sequence

  • str1str2Longest Common Sequence을 찾는다.
  • str1str2에서 Longest Common Sequence에 포함되지 않는 문자열을 차례대로 추가한다.
  • 추가하지 않은 문자열을 뒤에 차례대로 추가한다.
function shortestCommonSupersequence(str1: string, str2: string): string {
  const subsequence = longestCommonSubsequence(str1, str2);
 
  let supersequence = '';
  let [index1, index2] = [0, 0];
  for (const char of subsequence) {
    const endIndex1 = str1.indexOf(char, index1);
    const endIndex2 = str2.indexOf(char, index2);
    supersequence += str1.substring(index1, endIndex1) + str2.substring(index2, endIndex2) + char;
 
    [index1, index2] = [endIndex1 + 1, endIndex2 + 1];
  }
 
  return supersequence + str1.substring(index1) + str2.substring(index2);
}
 
function longestCommonSubsequence(str1: string, str2: string): string {
  const [m, n] = [str1.length, str2.length];
  const dp = Array.from({ length: m + 1 }, () => new Array<string>(n + 1).fill(''));
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + str1[i - 1];
      } else if (dp[i - 1][j].length < dp[i][j - 1].length) {
        dp[i][j] = dp[i][j - 1];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[m][n];
}

복잡도

  • mm: str1의 길이, nn: str2의 길이, LL: Longest Common Sequence의 길이.
  • 시간 복잡도: O(mn)O(m \cdot n)
  • 공간 복잡도: O(mnL)O(m \cdot n \cdot L)

더 효율적인 방법

  • dp 에 현재 subsequence를 저장하는 것이 아니라, subsequence의 길이만을 저장한다.
  • indexOf 과 같은 메서드를 사용하는 것이 아니라, 차례대로 확인한다.
function shortestCommonSupersequence(str1: string, str2: string): string {
  const [m, n] = [str1.length, str2.length];
  const dp = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
 
  let [i, j] = [m, n];
  const supersequence: string[] = [];
  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      supersequence.push(str1[i - 1]);
      i -= 1;
      j -= 1;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      supersequence.push(str1[i - 1]);
      i -= 1;
    } else {
      supersequence.push(str2[j - 1]);
      j -= 1;
    }
  }
  while (i > 0) {
    supersequence.push(str1[i - 1]);
    i -= 1;
  }
  while (j > 0) {
    supersequence.push(str2[j - 1]);
    j -= 1;
  }
  return supersequence.reverse().join('');
}

복잡도

  • mm: str1의 길이, nn: str2의 길이
  • 시간 복잡도: O(mn)O(m \cdot n)
  • 공간 복잡도: O(mn)O(m \cdot n)