Backtracking the table
- Algorithms course
- Advanced
- Lesson 11/56
- 4 min
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.
Practice 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")).
Starter code
def lcs_str(s1, s2):
# LCS string backtrackSample 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"))Expected output
AC
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Backtracking the table: match the terms
| Term | Meaning |
|---|---|
backtrack |
Backtrack |
match |
Match |
prepend |
Prepend |
direction |
Direction |
2 Where does backtracking start?
- Middle cell
- Top-left corner
- Bottom-right corner Correct answer
- First row
Explanation: Bottom-right corner.
3 Character add
result = s1[i - 1] + ____result = s1[i - 1] + resultExplanation: result is right.