Levenshtein Distance

1. One-Liner

Levenshtein distance is the minimum number of insertions, deletions, and substitutions needed to turn string A into B.

2. The Problem It Solves

Powers fuzzy matching, spell checking, diffing genes, and measuring similarity when alignment matters more than exact equality.

3. The Core Idea

Dynamic programming: dp[i][j] = edit distance between A[0..i) and B[0..j). If characters match, cost 0 from dp[i-1][j-1]; else take 1 + min of three neighboring states (delete, insert, replace).

4. How It Works (Table)

Step	What Happens
1	Initialize `dp[i][0]=i`, `dp[0][j]=j`.
2	For each `i,j`, if `A[i-1]==B[j-1]`, `dp[i][j]=dp[i-1][j-1]`.
3	Else `dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`.
4	Answer is `dp[n][m]`; space can roll to O(min(n,m)).

5. Dry Run Example

"kitten" → "sitting": substitute k→s, e→i, insert g at end → distance 3 (classic example).

6. Key Properties

Property	Value
Metric	Satisfies triangle inequality (true edit distance)
Weights	Damerau-Levenshtein adds transposition variant

7. Where It Is Used

Domain	Use
Search	Query correction
NLP	Alignment baselines
Bioinformatics	Simple sequence cost (with different costs)

8. Interview Tips

Trace parent pointers for optimal alignment. Mention O(nm) time and rolling array optimization.

9. Comparison with Other Algorithms

Variant	Extra ops
LCS	Longest subsequence (no replace cost model)
Hamming	Equal length, substitutions only

10. Complexity

Metric	Value
Time	O(`n·m`)
Space	O(`n·m`) full table; O(min(n,m)) with two rows

Implementation Example (PYTHON)

def levenshtein(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 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], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[n][m]