Hard

Shortest Common Supersequence

LAB

Return the shortest string that contains str1 and str2 as subsequences. If ties exist, return the lexicographically smallest result.

EXAMPLES

Example 1

Input
{
  "str1": "abac",
  "str2": "cab"
}

Output
"cabac"

FUNCTION SHAPE

str1: stringstr2: string→string

SOLUTION NOTE

First find LCS, then backtrack to build the supersequence. Include characters not in LCS from both strings, and shared characters once.

Reveal reference solution +

pythonREFERENCE

def shortestCommonSupersequence(self, s: str, t: str) -> str:
    m, n = len(s), len(t)

    @cache
    def dp(i, j):
        if i < 0 or j < 0: return 0
        if s[i] == t[j]:
            return 1 + dp(i-1, j-1)
        return max(dp(i-1, j), dp(i, j-1))

    # Backtrack to construct the answer
    i, j = m-1, n-1
    res = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            res.append(s[i])
            i -= 1
            j -= 1
        elif dp(i-1, j) >= dp(i, j-1):
            res.append(s[i])
            i -= 1
        else:
            res.append(t[j])
            j -= 1

    # Add remaining characters
    while i >= 0:
        res.append(s[i])
        i -= 1
    while j >= 0:
        res.append(t[j])
        j -= 1

    return ''.join(res[::-1])

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗