Distance Metrics

Skip to the problems!

Levenshtein distance

Given two strings A and B Levenshtein distance mesaures the minimum number of character replacements + insertions + deletions to transform A into B (or equivalently, B into A).

Example

\(\operatorname {lev} (\text{"raccoon"}, \text{"baboon"}) = 3\)

transformations

1. raccoon -> baccoon # (1)!
2. baccoon -> babcoon # (2)!
3. babcoon -> baboon  # (3)!

1. replace "r" with "b"
2. replace "c" with "b"
3. delete "c"

This example shows that "raccoon" can be transformed into "baboon" with three edits. It does not prove that three edits is the minimum necessary to get the job done.

For details on how Levenshtein distance is calculated, see the Wikipedia article.

Previous Next