Edit Distance

A spell-checker suggesting "did you mean 'kitten'" when you typed "sitten," or a ticker-symbol matcher tolerating one typo'd character, both need a numeric notion of "how different are these two strings." Edit distance (Levenshtein distance) is that number: the minimum count of single-character insertions, deletions, and substitutions to turn string $A$ into string $B$.

The idea: same table as LCS, one more option per cell

Define $dp[i][j]$ as the edit distance between the first $i$ characters of $A$ and the first $j$ characters of $B$. If the current characters match, no edit is needed here — inherit the diagonal cell unchanged. If they don't match, an edit is unavoidable, and you take the cheapest of the three possible edits:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } A_i = B_j \\ 1 + \min\big(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]\big) & \text{otherwise} \end{cases}$$

In words, the three options on a mismatch are: substitute $A_i$ for $B_j$ (diagonal cell plus one edit), delete $A_i$ (cell above plus one edit — $A$ gets one character shorter), or insert $B_j$ into $A$ (cell to the left plus one edit — $A$ gets one character longer, matching $B$'s prefix). The base cases are $dp[i][0] = i$ (delete all of $A$'s first $i$ characters) and $dp[0][j] = j$ (insert all of $B$'s first $j$ characters). Time and space are $O(mn)$, same shape as Longest Common Subsequence — the only difference is the extra "diagonal + 1" and "left + 1" options on a mismatch, versus LCS's plain max of two neighbors.

Worked example: "cat" to "cut"

Prefixes of $A$="cat" as rows 0-3, $B$="cut" as columns 0-3. Row 0 and column 0 are [0,1,2,3] (all inserts/deletes). Row 1 (A="c"): $j{=}1$ ('c' vs 'c') match → $dp[1][1]=dp[0][0]=0$. $j{=}2$ ('c' vs 'u') mismatch → $1+\min(dp[0][1],dp[0][2],dp[1][1])=1+\min(1,2,0)=1$. $j{=}3$ ('c' vs 't') mismatch → $1+\min(dp[0][2],dp[0][3],dp[1][2])=1+\min(2,3,1)=2$. Row 2 (A="ca"): $j{=}1$ ('a' vs 'c') mismatch → $1+\min(dp[1][0],dp[1][1],dp[2][0])=1+\min(1,0,2)=1$. Continuing similarly, $dp[2][2]=1$ (a vs u mismatch, best neighbor 0), $dp[2][3]=2$. Row 3 (A="cat"): $j{=}3$ ('t' vs 't') match → $dp[3][3]=dp[2][2]=1$. Answer: edit distance 1 — substitute 'a' for 'u'.

def edit_distance(a, b):                       # O(m*n) time and space
    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
    for j in range(n+1): dp[0][j] = 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-1], dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Where it shows up

Interview staples: edit distance itself (LeetCode 72), one edit distance, and DNA/text similarity variants. On a desk, fuzzy matching ticker symbols, company names, or instrument identifiers across data vendors with inconsistent formatting relies on edit distance (or its weighted variants) to decide "these are probably the same entity despite a typo," and it's a standard building block in entity-resolution pipelines for alternative data.