patternjavascriptModerate
Levenshtein distance: DP on a 2D grid for edit distance between strings
Viewed 0 times
levenshtein distanceedit distancespell checkfuzzy matchstring similaritydp table
Problem
Computing how similar two strings are (for spell checking, fuzzy matching, diff algorithms) requires edit distance. The recursive definition is intuitive but the naive implementation is exponential without DP.
Solution
Build a 2D DP table. dp[i][j] = edit distance between a[0..i] and b[0..j]. Base cases: empty string needs i/j insertions. Recurrence: if chars match, dp[i][j] = dp[i-1][j-1]; else take min of insert (dp[i][j-1]+1), delete (dp[i-1][j]+1), replace (dp[i-1][j-1]+1). Answer at dp[m][n].
Why
Each cell depends only on three previous cells. Computing all mn cells is O(mn). Space can be optimized to O(min(m,n)) by keeping only two rows at a time.
Gotchas
- The three operations are insert (into a to match b), delete (from a), and substitute — get the direction right
- For 1D space optimization, only keep the previous row (not the full matrix)
- Damerau-Levenshtein adds transposition as a fourth operation (swap adjacent chars) — closer to human typos
Code Snippets
Levenshtein distance with O(n) space
function editDistance(a, b) {
const m = a.length, n = b.length;
// Space-optimized: two rows
let prev = Array.from({length: n+1}, (_, j) => j);
for (let i = 1; i <= m; i++) {
const curr = [i];
for (let j = 1; j <= n; j++) {
if (a[i-1] === b[j-1]) curr[j] = prev[j-1];
else curr[j] = 1 + Math.min(prev[j-1], prev[j], curr[j-1]);
}
prev = curr;
}
return prev[n];
}Context
Spell checkers, fuzzy search, autocorrect, DNA sequence alignment, diff tools
Revisions (0)
No revisions yet.