Realm
sitting
gno.land/r/moul/x/daily/levenshteindemo/v1:kitten/sitting
Render
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 |
Source (qfile)
README.md gnomod.toml levenshteindemo.gno