Edit Distance
Minimum single-character edits (insert, delete, replace) to turn one string into another. Spell-checkers and fuzzy search rank candidates by exactly this number.
- Category
- Dynamic Programming
- Time complexity
- O(n·m)
- Space complexity
- O(n·m)
Pseudocode
grid: source × target same char: copy diagonal else 1 + min(ins, del, rep) 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])