Dynamic Programming • Traceback

Printing the Longest Common Subsequence

After populating the LCS DP table, learn how to reconstruct the actual string instead of just returning the max length.

Overview

Populating a DP table tells you the length of the optimal solution. Tracing backward through that table tells you the *elements* of that optimal solution.

The Starting Point

You always start your traceback from the final computed answer, which is at the bottom-right corner of the DP matrix: `dp[m][n]`.

The Logic

If characters match, that character is part of the LCS. Prepend it to the result and move diagonally UP-LEFT (`i-1, j-1`).

Mismatches

If characters don't match, we know the LCS must have come from either the cell ABOVE us or to the LEFT of us. We simply move to whichever has the larger value.

S1 \ S2	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

Code Tracker

:::

1let result = '';

2let i = s1.length, j = s2.length;

3while (i > 0 && j > 0) {

4 if (s1[i - 1] === s2[j - 1]) {

5 result = s1[i - 1] + result;

6 i--; j--;

7 } else {

8 if (dp[i - 1][j] > dp[i][j - 1]) {

9 i--;

10 } else {

11 j--;

12 }

13 }

14}

15return result;

Print Lcs

Print Lcs

Printing the Longest Common Subsequence

Overview

The Starting Point

The Logic

Mismatches

Printing the Longest Common Subsequence

Overview

The Starting Point

The Logic

Mismatches