[LeetCode] 1092. Shortest Common Supersequence (Python)

Problem

 

Solution

db
LCS (Longest Common Subsequence)

이 문제의 힌트를 보고 LCS 알고리즘을 사용한 문제라는 것을 알았다.

LCS 알고리즘에 대한 설명은 다른 블로그에서 더 자세하게 설명해두어서 참고했다!

https://chanhuiseok.github.io/posts/algo-34/

알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘

 

단 LCS 의 길이를 구하는 알고리즘이라서 LCS 문자를 찾으려면 역추적(back tracking)을 이용해서 구해야한다.

 

주어진 2개의 string의 LCS 를 구하는 규칙은 아래와 같다.

• 문자열을 비교하여 같았을 때
  • 현재 칸에 들어갈 값은 대각선 왼쪽 위의 값 + 1 이다.
• 문자열을 비교하여 달랐을 때
  • 현재 칸에 들어갈 값은 왼쪽과 위쪽의 값 중 더 큰 값이 들어간다.

이 규칙을 이용해서 2차 배열을 구하고 이 배열을 백트래킹해서 LCS 문자열을 찾는다.

문자열을 역추적할 때에는 a[i] == b[j] 라면 db[i-1][j-1] 위치로 이동하고, 그렇지 아니면 db[i-1][j], db[i][j-1] 중에서 큰 값으로 이동한다.

 

Code

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        dp = [[0] * (n+1) for _ in range(m+1)]

        #fill dp table for LCS algorithm
        for i in range(1, m+1):
            for j in range(1, n+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
        #Reconstruct answer from dp table
        i, j = m, n
        res = ''
        while i>0 or j>0:
            # str1 (top) 이 더 클때
            if i>0 and dp[i][j] == dp[i-1][j]:
                res += str1[i-1]
                i -= 1
            #str2 (left) 이 더 클때
            elif j>0 and dp[i][j] == dp[i][j-1]:
                res += str2[j-1]
                j -= 1
            #str1[i] == str2[j] 인 경우
            else:
                res += str1[i-1]
                i -= 1
                j -= 1
    
        return res[::-1]

 

 

 

Complexity

Time Complexity

- DP 테이블 채우기: O(m * n)

- 최단 공통 수열(SCS) 재구성: O(m + n) => while loop 돌면서 dp table backtracking

 

총 시간복잡도: O(m * n)

Space Complexity

 

• DP 테이블: O(m * n)
  • dp 테이블을 크기 (m+1) x (n+1) 배열로 저장.
• 결과 문자열: O(m + n)
  • 최악의 경우 두 문자열을 그대로 포함하는 SCS가 만들어질 수 있음.
• 총 공간복잡도: O(m * n)