Longest Common Subsequence and Edit Distance
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Comparing two strings is a table problem. Cell (i, j) answers the question for the first i letters of one string and the first j letters of the other, and each cell looks at three neighbours.
Longest common subsequence
A subsequence of a string is made by deleting zero or more characters and keeping the order of the rest. It is not a substring, which must be one unbroken piece of the string.
Two strings share letters in the same order, but not always side by side. Find the length of the longest such shared run. Let dp[i][j] be the answer for the first i letters of a and the first j letters of b.
def lcs(a, b): dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)] for i, x in enumerate(a, 1): for j, y in enumerate(b, 1): if x == y: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[-1][-1]Example 1 · Brute force with slices
def lcs_slow(a, b): if not a or not b: return 0 if a[-1] == b[-1]: return 1 + lcs_slow(a[:-1], b[:-1]) return max(lcs_slow(a[:-1], b), lcs_slow(a, b[:-1]))
print(lcs_slow("ABCB", "BDCB"))3
What this code does
- Compare the last letters. If equal, they belong to the answer. If not, drop the last letter of one string or the other and take the better result.
- Subproblems repeat, so the time grows like 2 to the power (m + n).
Example 2 · Remember answers with a cache
from functools import cache
def lcs_cached(a, b): @cache def go(i, j): if i == 0 or j == 0: return 0 if a[i - 1] == b[j - 1]: return 1 + go(i - 1, j - 1) return max(go(i - 1, j), go(i, j - 1))
return go(len(a), len(b))
print(lcs_cached("AGGTAB", "GXTXAYB"))4
What this code does
go(i, j)is the answer for the first i and j letters. The cache means each pair is solved once.- The result 4 is "GTAB". The recursion depth is about m + n, so very long strings need the table.
Example 3 · The table printed
a, b = "ABCB", "BDCB"dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]for i, x in enumerate(a, 1): for j, y in enumerate(b, 1): if x == y: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])for row in dp: print(row)[0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 1, 1, 1, 1] [0, 1, 1, 2, 2] [0, 1, 1, 2, 3]
What this code does
- The first row and column stay 0. The last row ends with 3, the length of the answer.
- Values never decrease along a row or down a column.
The table has (len(a) + 1) x (len(b) + 1) cells, each filled in constant time. The cost is O(m x n) time and space for strings of length m and n.
Read the table
Row 0 and column 0 are zero: an empty string shares nothing. When the two letters match, take the diagonal cell and add one. Otherwise take the larger of the cell above and the cell to the left. To get the string itself, walk back from the corner.
def lcs_text(a, b, dp): i, j, out = len(a), len(b), [] while i and j: if a[i - 1] == b[j - 1]: out.append(a[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] >= dp[i][j - 1]: i -= 1 else: j -= 1 return "".join(reversed(out))Example 4 · Rebuild the common letters
a, b = "ABCB", "BDCB"dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]for i, x in enumerate(a, 1): for j, y in enumerate(b, 1): dp[i][j] = dp[i - 1][j - 1] + 1 if x == y else max(dp[i - 1][j], dp[i][j - 1])i, j, out = len(a), len(b), []while i and j: if a[i - 1] == b[j - 1]: out.append(a[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] >= dp[i][j - 1]: i -= 1 else: j -= 1print("".join(reversed(out)))BCB
What this code does
- Start at the bottom-right. A match adds the letter and moves diagonally. Otherwise move towards the larger neighbour.
- Letters are collected backwards, so reverse them at the end.
Each step moves up, left or diagonally, so the walk takes at most m + n steps. It needs the full table.
Edit distance
Edit distance is the smallest number of single-character inserts, deletes and replacements that turn one string into another. It measures how different two strings are.
How many single-letter inserts, deletes or replacements turn word a into word b? The cost for the first i and j letters copies the diagonal when the letters match. Otherwise it adds one to the best of three moves.
def edit_distance(a, b): dp = [[i] + [0] * len(b) for i in range(len(a) + 1)] dp[0] = list(range(len(b) + 1)) for i, x in enumerate(a, 1): for j, y in enumerate(b, 1): if x == y: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[-1][-1]Example 5 · Edit distance of two words
def edit_distance(a, b): dp = [[i] + [0] * len(b) for i in range(len(a) + 1)] dp[0] = list(range(len(b) + 1)) for i, x in enumerate(a, 1): for j, y in enumerate(b, 1): if x == y: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[-1][-1]
print(edit_distance("kitten", "sitting"))print(edit_distance("", "abc"))print(edit_distance("same", "same"))3 3 0
What this code does
- kitten to sitting: replace k with s, replace e with i, insert g. That is 3 edits.
- An empty word needs 3 inserts to become "abc". Equal words need none.
Example 6 · Suggest the closest word
def edit_distance(a, b): dp = [[i] + [0] * len(b) for i in range(len(a) + 1)] dp[0] = list(range(len(b) + 1)) for i, x in enumerate(a, 1): for j, y in enumerate(b, 1): if x == y: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[-1][-1]
words = ["account", "balance", "payment", "invoice"]typed = "paymnet"print(min(words, key=lambda w: edit_distance(typed, w)))payment
What this code does
minwith akeypicks the word with the smallest edit distance, which is how simple spell-checkers rank suggestions.- Swapping two letters costs 2 edits here, still far less than any other word.
Column 0 holds i deletes and row 0 holds j inserts. Above is a delete, left is an insert and the diagonal is a replace. The cost is O(m x n).
Keep only two rows
Row i needs only row i - 1, so keep a previous row and a current row. Space drops from m x n to n. The price is that the full table is gone, so the actual string can no longer be rebuilt.
def lcs_two_rows(a, b): prev = [0] * (len(b) + 1) for x in a: cur = [0] for j, y in enumerate(b, 1): if x == y: cur.append(prev[j - 1] + 1) else: cur.append(max(prev[j], cur[j - 1])) prev = cur return prev[-1]Example 7 · Two rows on longer strings
def lcs_two_rows(a, b): prev = [0] * (len(b) + 1) for x in a: cur = [0] for j, y in enumerate(b, 1): if x == y: cur.append(prev[j - 1] + 1) else: cur.append(max(prev[j], cur[j - 1])) prev = cur return prev[-1]
print(lcs_two_rows("abc" * 100, "acb" * 100))200
What this code does
- Two lists of 301 numbers replace a table of 301 x 301 cells.
- Use this when only the length is needed. The full table is required to print the string.
Put the shorter string in b to keep the rows short. The time is still O(m x n).
Next step
Check your understanding
12 quick questions