Edit Distance (Levenshtein)
Time: O(mn)Space: O(mn)Minimum number of single-character edits (insertions, deletions, replacements) to transform one string into another. Used in spell checkers, diff tools, and DNA alignment.
SlowFast
1 / 51DP Table
s
i
t
t
i
n
g
0
1
2
3
4
5
6
7
k
1
0
0
0
0
0
0
0
i
2
0
0
0
0
0
0
0
t
3
0
0
0
0
0
0
0
t
4
0
0
0
0
0
0
0
e
5
0
0
0
0
0
0
0
n
6
0
0
0
0
0
0
0
Inputs
Phase
Fill Table
Description
Initialize: dp[i][0]=i (delete i chars), dp[0][j]=j (insert j chars). Transforming "kitten" → "sitting".
Legend
Default
Active cell
Backtrack path
Header