String dynamic programming · recursion + memoization

Shortest common supersequence

Input: two strings A and B. Output: a shortest string containing both A and B as subsequences. The characters of each input must stay in order, but other characters may appear between them. There can be several shortest answers; return any one. Empty strings are allowed.

A = “AB”B = “BC”One answer = “ABC”

The recursive question

What is the shortest merge of these suffixes?

solve(i, j) returns a shortest common supersequence of A[i:] and B[j:]. Each call writes the next output character. Memoization stores the shortest result for each pair of suffix positions.

Base case

If one string is exhausted, append the entire unused suffix of the other.

Matching letters

Write the shared letter once, then advance both indices.

Different letters

Try writing A’s letter first or B’s letter first; keep the shorter result.

There are at most (m + 1)(n + 1) memo states. Because each state constructs and stores a string of up to m + n characters, this direct implementation takes O(mn(m + n)) time and space in the worst case.

Interactive call trace

See each merge decision

Follow the recursive branches and watch solved suffix pairs fill the memo table.

Memoized suffix states

Current character / stateMatching charactersSaved memo value

A · indices

B · indices

Memo table · row i, column j

Active recursive call stack

Python reference

From recursion to memoization

Both versions construct a shortest string. The animation follows the memoized version. On a tie, it chooses the A-first branch.

from functools import cache

def shortest_common_supersequence(a: str, b: str) -> str:
    @cache
    def solve(i: int, j: int) -> str:
        if i == len(a):
            return b[j:]
        if j == len(b):
            return a[i:]
        if a[i] == b[j]:
            return a[i] + solve(i + 1, j + 1)

        from_a = a[i] + solve(i + 1, j)
        from_b = b[j] + solve(i, j + 1)
        return from_a if len(from_a) <= len(from_b) else from_b

    return solve(0, 0)

print(shortest_common_supersequence("AB", "BC"))  # ABC

def scs_recursive(a: str, b: str) -> str:
    def solve(i: int, j: int) -> str:
        if i == len(a):
            return b[j:]
        if j == len(b):
            return a[i:]
        if a[i] == b[j]:
            return a[i] + solve(i + 1, j + 1)

        from_a = a[i] + solve(i + 1, j)
        from_b = b[j] + solve(i, j + 1)
        return from_a if len(from_a) <= len(from_b) else from_b

    return solve(0, 0)

Plain recursion explores the same suffix pairs repeatedly and can take exponential time.