Levenshtein distance
Transforming sunday → saturday
- Edit distance:
3single-character edits (insert / delete / substitute) - Similarity:
63%
DP table
Each cell d[i][j] is the distance between the first i runes of sunday and the first j runes of saturday. The bottom-right cell is the answer.
| ε | s |
a |
t |
u |
r |
d |
a |
y |
|
|---|---|---|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s |
1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
u |
2 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
n |
3 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
d |
4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
a |
5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 | 4 |
y |
6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 | 3 |
