leetcode 1092. Shortest Common Supersequence

문제

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

두 문자열 str1과 str2가 주어졌을 때, str1과 str2를 모두 부분 수열로 가지는 가장 짧은 문자열을 반환하세요. 만약 유효한 문자열이 여러 개라면, 그중 하나를 반환하면 됩니다.

문자열 s가 문자열 t의 부분 수열이라는 것은 t에서 일부 문자(0개일 수도 있음)를 삭제했을 때 문자열 s가 되는 것을 의미합니다.

---

예시

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
- str2에서 c
- str1과 str2에서 ab
- str1에서 나머지 ac

---

제한

• $1 <= str1.length, str2.length <= 1000$
• str1과 str2는 영어 소문자로만 구성됩니다.

---

풀이법

• LCS풀이법을 사용하되, 바로 문자열을 구성하지 않고 길이를 저장한 뒤 차후 새로 구성한다.
• 바로 구성하면 풀이는 되지만, 메모리 초과가 나온다.

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:

        S1 = len(str1)
        S2 = len(str2)

        cache = [[0] * (S2 + 1) for _ in range(S1 + 1)]

        def dp(first_index: int, second_index: int):
            if first_index == S1 and second_index == S2:
                return 0

            if cache[first_index][second_index] != 0:
                return cache[first_index][second_index]

            ans = ""

            if first_index >= S1:
                ans = S2 - second_index
            elif second_index >= S2:
                ans = S1 - first_index
            elif str1[first_index] == str2[second_index]:
                ans = 1 + dp(first_index + 1, second_index + 1)
            else:
                ans = min(1 + dp(first_index + 1, second_index), 1 + dp(first_index, second_index + 1))

            cache[first_index][second_index] = ans

            return ans

        dp(0, 0)

        def reconstruction(first_index, second_index):
            if first_index == S1 and second_index == S2:
                return ""
            elif first_index >= S1:
                return str2[second_index:]
            elif second_index >= S2:
                return str1[first_index:]
            elif str1[first_index] == str2[second_index]:
                return str1[first_index] + reconstruction(first_index + 1, second_index + 1)
            else:
                len1 = cache[first_index + 1][second_index]
                len2 = cache[first_index][second_index + 1]

                if len1 < len2:
                    return str1[first_index] + reconstruction(first_index + 1, second_index)
                else:
                    return str2[second_index] + reconstruction(first_index, second_index + 1)

        return reconstruction(0, 0)

• 정돈한 버전

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        S1 = len(str1)
        S2 = len(str2)

        dp = [
            [0] * (S2 + 1) for _ in range(S1 + 1)
        ]

        def dynamic(first_index, second_index):
            if first_index == S1 and second_index == S2:
                return 0

            if dp[first_index][second_index] != 0:
                return dp[first_index][second_index]

            ans = 0

            if first_index >= S1:
                ans = S2 - second_index
            elif second_index >= S2:
                ans = S1 - first_index
            elif str1[first_index] == str2[second_index]:
                ans = 1 + dynamic(first_index + 1, second_index + 1)
            else:
                first = 1 + dynamic(first_index, second_index + 1)
                second = 1 + dynamic(first_index + 1, second_index)
                ans = min(first, second)

            dp[first_index][second_index] = ans

            return ans

        dynamic(0, 0)

        def reconstruct(first_index, second_index):
            if first_index == S1 and second_index == S2:
                return ""
            elif first_index >= S1:
                return str2[second_index:]
            elif second_index >= S2:
                return str1[first_index:]
            elif str1[first_index] == str2[second_index]:
                return str1[first_index] + reconstruct(first_index + 1, second_index + 1)
            else:
                len1 = dp[first_index + 1][second_index]
                len2 = dp[first_index][second_index + 1]
                if len1 < len2:
                    return str1[first_index] + reconstruct(first_index + 1, second_index)
                else:
                    return str2[second_index] + reconstruct(first_index, second_index + 1)

        return reconstruct(0, 0)