Levenshtein Distance
The classic string-edit-distance metric: minimum insertions, deletions, and substitutions (each cost 1) to transform one string into another. Identical recurrence to Edit Distance — this is simply its formal name.
- Category
- Strings
- Time complexity
- O(n·m)
- Space complexity
- O(n·m)
Pseudocode
grid: source × target same char: copy diagonal else: 1 + min(delete, insert, substitute) distance at bottom-right
Reference implementation
if A[i] == B[j]:
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])