Two-Sequence Alignment (LCS / Edit Distance)

Foundations

In the first lesson, the table's two indexes were a cell's row and column. Now, what if they are positions in two different sequences, and each cell compares one prefix of the first with one prefix of the second?

Let dp[i][j] describe the prefixes s[:i] and t[:j]: the first i items of s and the first j of t. If their last items match, the answer extends the diagonal cell, dp[i - 1][j - 1]; if not, it is the better of dropping the last item of s, the cell above, or of t, the cell to the left. Row 0 and column 0 are empty prefixes, the base cases.

Take s = nums = [7, 1, 5, 3, 6] and t = [1, 3, 7, 6], and find their longest common subsequence. The 1s match, so dp[2][1] = 1; the 3s extend that diagonal to 2 at dp[4][2]; the 6s extend it to 3 at dp[5][4]. Every other cell copies the better neighbor, and the corner holds 3: the subsequence 1, 3, 6.

Case Scenario

Longest Common Subsequence compares two strings, text1 and text2, and asks for the length of the longest sequence of letters that appears in both in order, not necessarily side by side. For text1 = "abcde" and text2 = "ace", the matches a, c, and e each extend a diagonal of the table, so the answer is 3.

The direct approach recurses on both strings: on a match, advance both; on a mismatch, try dropping a letter from each side and keep the better. The same pair of positions is reached by many different drop orders, so the calls grow exponentially, about 2^(m + n), though only m · n pairs of prefixes exist.