1092. Shortest Common Supersequence - Explanation

1. Dynamic Programming (Top-Down)

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        cache = [[None] * (len(str2) + 1) for _ in range(len(str1) + 1)]
        str1 = list(str1)
        str2 = list(str2)

        def dfs(i: int, j: int) -> list:
            if cache[i][j] is not None:
                return cache[i][j]
            if i == len(str1):
                cache[i][j] = str2[j:][::-1]
                return cache[i][j]
            if j == len(str2):
                cache[i][j] = str1[i:][::-1]
                return cache[i][j]

            if str1[i] == str2[j]:
                res = dfs(i + 1, j + 1) + [str1[i]]
            else:
                s1 = dfs(i + 1, j)
                s2 = dfs(i, j + 1)
                if len(s1) < len(s2):
                    res = s1 + [str1[i]]
                else:
                    res = s2 + [str2[j]]

            cache[i][j] = res
            return res

        return ''.join(reversed(dfs(0, 0)))

Time & Space Complexity

Time complexity: $O(n * m * min(n, m))$
Space complexity: $O(n * m * min(n, m))$

Where $n$ and $m$ are the lengths of the strings $str1$ and $str2$ respectively.

2. Dynamic Programming (Top-Down) + Tracing

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

        def dfs(i, j):
            if dp[i][j] != -1:
                return dp[i][j]
            if i == n:
                dp[i][j] = m - j
                return dp[i][j]
            if j == m:
                dp[i][j] = n - i
                return dp[i][j]
            if str1[i] == str2[j]:
                dp[i][j] = 1 + dfs(i + 1, j + 1)
            else:
                dp[i][j] = 1 + min(dfs(i + 1, j), dfs(i, j + 1))
            return dp[i][j]

        dfs(0, 0)

        def build_scs(i, j):
            res = []
            while i < n or j < m:
                if i == n:
                    res.extend(str2[j:])
                    break
                if j == m:
                    res.extend(str1[i:])
                    break
                if str1[i] == str2[j]:
                    res.append(str1[i])
                    i += 1
                    j += 1
                elif dp[i + 1][j] < dp[i][j + 1]:
                    res.append(str1[i])
                    i += 1
                else:
                    res.append(str2[j])
                    j += 1
            return res

        return ''.join(build_scs(0, 0))

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ and $m$ are the lengths of the strings $str1$ and $str2$ respectively.

3. Dynamic Programming (Bottom-Up)

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

        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0:
                    dp[i][j] = str2[:j]
                elif j == 0:
                    dp[i][j] = str1[:i]
                elif str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + str1[i - 1]
                else:
                    if len(dp[i - 1][j]) < len(dp[i][j - 1]):
                        dp[i][j] = dp[i - 1][j] + str1[i - 1]
                    else:
                        dp[i][j] = dp[i][j - 1] + str2[j - 1]

        return dp[n][m]

Time & Space Complexity

Time complexity: $O(n * m * min(n, m))$
Space complexity: $O(n * m * min(n, m))$

Where $n$ and $m$ are the lengths of the strings $str1$ and $str2$ respectively.

4. Dynamic Programming (Bottom-Up) + Tracing

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

        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0:
                    dp[i][j] = j
                elif j == 0:
                    dp[i][j] = i
                elif str1[i - 1] == str2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

        res = []
        i, j = n, m
        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

        while i > 0:
            res.append(str1[i - 1])
            i -= 1

        while j > 0:
            res.append(str2[j - 1])
            j -= 1

        return ''.join(reversed(res))

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ and $m$ are the lengths of the strings $str1$ and $str2$ respectively.