DPDynamic Programming
Edit Distance (Levenshtein)
Minimum number of insertions, deletions, and substitutions to turn one string into another via a 2D prefix table.
| s | i | t | t | i | n | g | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| k | 1 | · | · | · | · | · | · | · |
| i | 2 | · | · | · | · | · | · | · |
| t | 3 | · | · | · | · | · | · | · |
| t | 4 | · | · | · | · | · | · | · |
| e | 5 | · | · | · | · | · | · | · |
| n | 6 | · | · | · | · | · | · | · |
1/44Turning a prefix into the empty string costs one deletion per character (column 0); building it from empty costs one insertion per character (row 0).
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Edit Distance →
1dp[i][0] = i; dp[0][j] = j2for i in 1 .. m: for j in 1 .. n:3 if A[i] == B[j]: dp[i][j] = dp[i-1][j-1]4 else: dp[i][j] = 1 + min(dp[i-1][j-1] replace, dp[i-1][j] delete, dp[i][j-1] insert)5traceback from dp[m][n]Variables
m6
n7
Complexity
best O(n·m)
avg O(n·m)
worst O(n·m)
space O(min(n, m))
Speed