Levenshtein distance
Transforming gno → gnoland
- Edit distance:
4single-character edits (insert / delete / substitute) - Similarity:
43%
DP table
Each cell d[i][j] is the distance between the first i runes of gno and the first j runes of gnoland. The bottom-right cell is the answer.
| ε | g |
n |
o |
l |
a |
n |
d |
|
|---|---|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
g |
1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
n |
2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
o |
3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
