Levenshtein Distance

The Levenshtein distance is a measure of the difference between two strings. It indicates how many single-character operations are needed to transform one string into the other. The allowed operations are:

1. Insertion of a character

2. Deletion of a character

3. Substitution of one character with another

Example:

The Levenshtein distance between "house" and "mouse" is 1, since only one letter (h → m) needs to be changed.

Applications:

Levenshtein distance is used in many areas, such as:

• Spell checking (suggesting similar words)

• DNA sequence comparison

• Plagiarism detection

• Fuzzy searching in databases or search engines

Formula (recursive, simplified):

For two strings a and b of lengths i and j:

lev(a, b) = min(
  lev(a-1, b) + 1,        // deletion
  lev(a, b-1) + 1,        // insertion
  lev(a-1, b-1) + cost    // substitution (cost = 0 if characters are equal; else 1)
)

There are also more efficient dynamic programming algorithms to compute it.