Levenshtein distance

Transforming flaw → lawn

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

← back