Levenshtein distance

Transforming kitten → sitting

• Edit distance: 3 single-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

← back