Shortest Common Supersequence — LCS + Reconstruct

Problem

Return the shortest string that has both str1 and str2 as subsequences.

Approach

Length of SCS = m + n - LCS(m,n). Reconstruct by backtracking through LCS DP table.

Time: O(mn) | Space: O(mn)

Solutions

Python

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)]
        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])
        res=[]; i,j=m,n
        while i>0 and j>0:
            if str1[i-1]==str2[j-1]: res.append(str1[i-1]); i-=1; j-=1
            elif dp[i-1][j]>dp[i][j-1]: res.append(str1[i-1]); i-=1
            else: res.append(str2[j-1]); j-=1
        res.extend(reversed(str1[:i])); res.extend(reversed(str2[:j]))
        return ''.join(reversed(res))

Complexity

Time: O(mn) | Space: O(mn)