[LeetCode] 1092. Shortest Common Supersequence (Python)

 

난이도: Hard

Problem Description

---

 

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.

 

Problem Example

---

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

 

Constraints

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

 

✏️ Solution

---

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

        dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(m+1):
            for j in range(n+1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                elif str1[j-1] == str2[i-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        #for d in dp:
        #    print(d)
        q = deque([(m,n)])

        sub_sequence = ''
        while q:
            x, y = q.popleft()
            if dp[x][y] == 0:
                break

            if dp[x-1][y] != dp[x][y] and dp[x][y-1] != dp[x][y]:
                sub_sequence += str2[x-1]
                q.append((x-1, y-1))
            elif dp[x-1][y] == dp[x][y]:
                q.append((x-1,y))
            elif dp[x][y-1] == dp[x][y]:
                q.append((x, y-1))

        sub_sequence = sub_sequence[::-1]
        
        answer = ''
        i, j = 0, 0
        for ss in sub_sequence:
            while ss != str1[i]:
                answer += str1[i]
                i+=1
            while ss != str2[j]:
                answer += str2[j]
                j+=1
            
            answer += ss
            i+=1
            j+=1
        
        answer += str1[i:] + str2[j:]

        return answer

 

어려운 문제였다...

 

`LCS`(Longest Common Subsequence) 알고리즘을 써서 푸는 문제인 것 같긴 해서 무작정 `LCS`를 구하긴 했는데(위 코드에서 sub_sequence), 이 뒤에 어떻게 해서 답을 구해야할지 감이 잘 오질 않았다.

 

이것 저것 다 해보다가 가능한 답이 여러가지이면 그 중 아무거나 반환을 해도 된다고 해서, 문자열을 순회하면서 `LCS`의 문자를 순서대로 포함시켰다.
즉, `sub_sequence`의 문자를 차례대로 `str1`, `str2`에서 찾아가며 해당 문자 이전에 등장하는 문자들은 `answer`에 추가해 주었다.

 

`sub_sequence`의 모든 문자를 확인했으면 마지막에 `str1`과 `str2`의 남은 문자들을 `answer`에 추가해주었다.

 

마지막에 이러한 answer를 반환하여 정답을 맞출 수 있었다.

 

어려운 문제였지만, LCS를 활용한 변형 문제에 대한 이해를 높일 수 있는 문제였던 것 같다! 😃

 

 

⚙️ Runtime & Memory

---

 

 

---

문제: 1092. Shortest Common Supersequence

 

깃허브: github

algorithmPractice/LeetCode/1170-shortest-common-supersequence at main · laewonJeong/algorithmPractice