Problem statement

https://leetcode.com/problems/shortest-common-supersequence/

Solution

The idea is to find the longest common subsequence first and then using our dp table we can reconstruct answer: if we have str[x] == str[y], we reduce x and y by one. If we have dp(x, y) == dp(x, y-1) + 1, we reduce y by one. In opposite case we reduce x by one.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def shortestCommonSupersequence(self, str1, str2):
        m, n = len(str1), len(str2)
        
        @lru_cache(None)
        def dp(i, j):
            if i == -1: return j + 1
            if j == -1: return i + 1
            if str1[i] == str2[j]:
                return dp(i-1, j-1) + 1
            return min(dp(i-1, j), dp(i, j-1)) + 1
            
        x, y = m - 1, n - 1
        ans = ""
        while (x, y) != (-1, -1):
            if x >= 0 and y >= 0 and str1[x] == str2[y]:
                ans += str1[x]
                x, y = x - 1, y - 1
            else:
                if y >= 0 and dp(x, y) == dp(x, y-1) + 1:
                    ans += str2[y]
                    y -= 1
                else:
                    ans += str1[x]
                    x -= 1
        
        return ans[::-1]