LCS & edit distance

The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same order, not necessarily contiguously. For 'abcde' and 'ace' it is 'ace', length 3.

Edit distance (Levenshtein distance) is the minimum number of single-character inserts, deletes and replacements to turn one string into another. 'horse' to 'ros' needs 3: replace h with r, delete r, delete e.

Both use the same table shape: (m + 1) x (n + 1), where row 0 and column 0 represent empty prefixes. Each cell looks at whether the last characters a[i-1] and b[j-1] match and then at three neighbours: up, left and diagonal.

1. 1Define dp[i][j] over prefixes: a[:i] and b[:j]. Size (m + 1) x (n + 1).
2. 2LCS base: row 0 and column 0 are 0 (an empty string has nothing in common). Edit distance base: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).
3. 3LCS transition: if a[i-1] == b[j-1], dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
4. 4Edit distance transition: if the characters match, dp[i][j] = dp[i-1][j-1]; otherwise 1 + min(dp[i-1][j] (delete from a), dp[i][j-1] (insert into a), dp[i-1][j-1] (replace)).
5. 5Fill row by row; the answer is dp[m][n]. To reconstruct the subsequence or the edit script, walk back from (m, n) following the choice made at each cell.
6. 6Each row only needs the previous row, so space can drop to O(min(m, n)) when you only need the number.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]


def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                   # delete all of a[:i]
    for j in range(n + 1):
        dp[0][j] = j                   # insert all of b[:j]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete
                                   dp[i][j - 1],      # insert
                                   dp[i - 1][j - 1])  # replace
    return dp[m][n]

# lcs("abcde", "ace") -> 3
# edit_distance("horse", "ros") -> 3

Both fill an (m + 1) x (n + 1) table of prefixes in O(m x n) time. Keeping only two rows reduces space to O(n) when you only need the value, not the alignment.

Cost: O(m x n) time; O(m x n) space with the full table (needed to reconstruct), O(min(m, n)) with two rows.