Levenshtein distance
Transforming kitten → sitting
- Edit distance:
3single-character edits (insert / delete / substitute) - Similarity:
57%
DP table
Each cell d[i][j] is the distance between the first i runes of kitten and the first j runes of sitting. The bottom-right cell is the answer.
| ε | s |
i |
t |
t |
i |
n |
g |
|
|---|---|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
k |
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
i |
2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
t |
3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
t |
4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
e |
5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
n |
6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
