Levenshtein distance
Transforming flaw → lawn
- Edit distance:
2single-character edits (insert / delete / substitute) - Similarity:
50%
DP table
Each cell d[i][j] is the distance between the first i runes of flaw and the first j runes of lawn. The bottom-right cell is the answer.
| ε | l |
a |
w |
n |
|
|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 |
f |
1 | 1 | 2 | 3 | 4 |
l |
2 | 1 | 2 | 3 | 4 |
a |
3 | 2 | 1 | 2 | 3 |
w |
4 | 3 | 2 | 1 | 2 |
