[Algorithm] Strings - Levenshtein Distance

Levenshtein Distance?

Explanation:
Levenshtein Distance is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into another. It is commonly used to measure the similarity between two strings and has applications in natural language processing, spell checking, and DNA sequence analysis.

Use Cases:

• Spell Checking: Used to detect and correct spelling errors by measuring the distance between the input word and the correct word.
• String Similarity: Useful in text comparison, data deduplication, and search engines to determine how closely related two strings are.
• DNA Sequence Analysis: Used to compare differences between DNA sequences and calculate evolutionary distances or mutation counts.

JavaScript Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function levenshteinDistance(str1, str2) {
  const len1 = str1.length;
  const len2 = str2.length;

  const dp = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0));

  // Initialize: transformation cost for empty strings
  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // No cost if characters match
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1, // Deletion
          dp[i][j - 1] + 1, // Insertion
          dp[i - 1][j - 1] + 1
        ); // Substitution
      }
    }
  }

  return dp[len1][len2];
}

// Example usage
console.log(levenshteinDistance("kitten", "sitting")); // Output: 3

Explanation:

• The dp array stores the cost of transforming substrings.
• When characters match, no additional cost is incurred. If they don’t, we calculate the minimum cost between insertion, deletion, or substitution.
• The final result at dp[len1][len2] gives the minimum number of edits needed to convert str1 to str2.

Rust Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
fn levenshtein_distance(str1: &str, str2: &str) -> usize {
    let len1 = str1.len();
    let len2 = str2.len();

    let mut dp = vec![vec![0; len2 + 1]; len1 + 1];

    // Initialize: transformation cost for empty strings
    for i in 0..=len1 {
        dp[i][0] = i;
    }
    for j in 0..=len2 {
        dp[0][j] = j;
    }

    for i in 1..=len1 {
        for j in 1..=len2 {
            if str1.as_bytes()[i - 1] == str2.as_bytes()[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]; // No cost if characters match
            } else {
                dp[i][j] = std::cmp::min(
                    dp[i - 1][j] + 1, // Deletion
                    std::cmp::min(
                        dp[i][j - 1] + 1, // Insertion
                        dp[i - 1][j - 1] + 1 // Substitution
                    )
                );
            }
        }
    }

    dp[len1][len2]
}

fn main() {
    let str1 = "kitten";
    let str2 = "sitting";
    println!("{}", levenshtein_distance(str1, str2)); // Output: 3
}

Explanation:

• The Rust code uses dynamic programming to compute the Levenshtein distance between two strings.
• The dp array stores the transformation costs, where we calculate the minimum cost between insertion, deletion, or substitution operations.

Summary:

Levenshtein Distance is an algorithm that calculates the minimum number of edits needed to transform one string into another. It is useful in applications such as spell checking, measuring string similarity, and DNA sequence analysis. The algorithm works by dynamically calculating the minimum cost of edit operations (insertion, deletion, substitution) between characters.