Backtracking the table

Trace the LCS back from the table.

Backtracking

After filling the DP table, we backtrack from the bottom-right corner to recover the LCS string.

On a match cell we prepend the character; else we move to the larger of left/top.

Backtracking gives the LCS itself, not just the length.

Direction choice

If no match, move toward the larger of dp[i-1][j] and dp[i][j-1]. If equal, either works.

The direction choice determines which LCS variant we get; there may be multiple LCS.

Prepending characters during backtracking preserves the correct order.

Exercise LCS string backtrack

Write lcs_str(s1, s2). Use a DP table + backtracking to recover the LCS string. Print AC with print(lcs_str("ABC", "AC")).

Show example solution

def lcs_str(s1, s2):
    # LCS string backtrack
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            result.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))
print(lcs_str("ABC", "AC"))

Test yourself

Backtracking the table: match the terms

backtrack

Backtrack
match

Match
prepend

Prepend
direction

Direction
Where does backtracking start?
- Middle cell
- Top-left corner
- Bottom-right corner
- First row
Show answer

Bottom-right corner — Bottom-right corner.

Character add

result = s1[i - 1] + ____

Show answer

result = s1[i - 1] + result

Next lesson: Summary - LCS

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies