Edit Distance Problem Levenshtein in DSA Rust

Mental Model

Find the smallest number of changes needed to turn one word into another by adding, removing, or changing letters.

Analogy: Imagine fixing a typo in a word by either erasing a letter, writing a new one, or changing a wrong letter to the right one, counting each fix as one step.

word1: c a t
word2: c a r

Matrix:
    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  1

Dry Run Walkthrough

Input: word1: "cat", word2: "car"

Goal: Calculate the minimum steps to change "cat" into "car" using insert, delete, or replace.

Step 1: Initialize matrix with sizes (len(word1)+1) x (len(word2)+1) and fill first row and column with index values

    ''  c  a  r
''  0  1  2  3
c   1  _  _  _
a   2  _  _  _
t   3  _  _  _

Why: We start with empty strings and count how many edits to get from empty to prefixes

Step 2: Compare 'c' (word1[0]) and 'c' (word2[0]), they match, so cost is 0; set matrix[1][1] = matrix[0][0] = 0

    ''  c  a  r
''  0  1  2  3
c   1  0  _  _
a   2  _  _  _
t   3  _  _  _

Why: No change needed when letters match

Step 3: Compare 'c' and 'a', they differ; calculate min of insert(1+matrix[1][1]), delete(1+matrix[0][2]), replace(1+matrix[0][1]) = min(1+0,1+2,1+1)=1; set matrix[1][2] = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  _
a   2  _  _  _
t   3  _  _  _

Why: Choose cheapest edit operation

Step 4: Compare 'c' and 'r', differ; min(insert, delete, replace) = min(1+1,1+3,1+2)=2; set matrix[1][3] = 2

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  _  _  _
t   3  _  _  _

Why: Continue filling first row

Step 5: Compare 'a' and 'c', differ; min(insert, delete, replace) = min(1+1,1+0,1+1)=1; set matrix[2][1] = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  _  _
t   3  _  _  _

Why: Fill second row first column

Step 6: Compare 'a' and 'a', match; set matrix[2][2] = matrix[1][1] = 0

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  _
t   3  _  _  _

Why: No edit needed for matching letters

Step 7: Compare 'a' and 'r', differ; min(insert, delete, replace) = min(1+0,1+2,1+1)=1; set matrix[2][3] = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  _  _  _

Why: Fill second row last column

Step 8: Compare 't' and 'c', differ; min(insert, delete, replace) = min(1+2,1+2,1+1)=2; set matrix[3][1] = 2

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  _  _

Why: Fill third row first column

Step 9: Compare 't' and 'a', differ; min(insert, delete, replace) = min(1+0,1+2,1+1)=1; set matrix[3][2] = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  _

Why: Fill third row second column

Step 10: Compare 't' and 'r', differ; min(insert, delete, replace) = min(1+1,1+1,1+0)=1; set matrix[3][3] = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  1

Why: Fill last cell with minimum edits

Result:

Final matrix:
    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  1

Minimum edit distance = 1

Annotated Code

DSA Rust

fn levenshtein_distance(word1: &str, word2: &str) -> usize {
    let len1 = word1.len();
    let len2 = word2.len();
    let w1: Vec<char> = word1.chars().collect();
    let w2: Vec<char> = word2.chars().collect();

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

    for i in 0..=len1 {
        dp[i][0] = i; // cost of deleting all chars from word1 prefix
    }
    for j in 0..=len2 {
        dp[0][j] = j; // cost of inserting all chars to match word2 prefix
    }

    for i in 1..=len1 {
        for j in 1..=len2 {
            if w1[i - 1] == w2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]; // no cost if chars match
            } else {
                dp[i][j] = 1 + std::cmp::min(
                    dp[i - 1][j].min(dp[i][j - 1]), // delete or insert
                    dp[i - 1][j - 1],               // replace
                );
            }
        }
    }

    dp[len1][len2]
}

fn main() {
    let word1 = "cat";
    let word2 = "car";
    let dist = levenshtein_distance(word1, word2);
    println!("Minimum edit distance between '{}' and '{}' is {}", word1, word2, dist);
}

dp[i][0] = i; // cost of deleting all chars from word1 prefix

initialize first column with deletion costs

dp[0][j] = j; // cost of inserting all chars to match word2 prefix

initialize first row with insertion costs

if w1[i - 1] == w2[j - 1] { dp[i][j] = dp[i - 1][j - 1]; }

no edit cost if characters match

dp[i][j] = 1 + std::cmp::min(dp[i - 1][j].min(dp[i][j - 1]), dp[i - 1][j - 1]);

choose minimum cost among delete, insert, replace plus one edit

Output

Minimum edit distance between 'cat' and 'car' is 1

Complexity Analysis

Time: O(m*n) because we fill a matrix of size m by n where m and n are lengths of the two words

Space: O(m*n) because we store the edit distances for all prefix pairs in a 2D matrix

vs Alternative: Compared to a naive recursive approach that repeats calculations, this dynamic programming method avoids repeated work and is much faster

Edge Cases

One or both words are empty strings

Distance equals the length of the other word (all insertions or deletions)

DSA Rust

dp[i][0] = i; // cost of deleting all chars from word1 prefix

Words are identical

Distance is zero because no edits are needed

DSA Rust

if w1[i - 1] == w2[j - 1] { dp[i][j] = dp[i - 1][j - 1]; }

Words differ by all characters

Distance equals the length of the longer word because all characters must be replaced

DSA Rust

dp[i][j] = 1 + std::cmp::min(dp[i - 1][j].min(dp[i][j - 1]), dp[i - 1][j - 1]);

When to Use This Pattern

When you need to find how similar two strings are by counting minimum edits, reach for the Levenshtein distance pattern because it systematically counts insertions, deletions, and replacements.

Common Mistakes

Mistake: Not initializing the first row and column of the matrix properly
Fix: Set dp[i][0] = i and dp[0][j] = j to represent base cases of empty prefixes

Mistake: Mixing up indices when accessing characters or matrix cells
Fix: Remember dp indices are offset by one compared to string indices because dp includes empty prefix

Summary

Calculates the minimum number of edits to change one word into another using insert, delete, or replace.

Use when you want to measure how different two strings are or find the minimal edits to convert one to the other.

The key insight is building a matrix that stores solutions for smaller prefixes and uses them to solve bigger problems.

Practice

1. What does the Levenshtein distance between two strings measure?

easy

A. The minimum number of single-character edits to change one string into the other

B. The maximum number of matching characters between two strings

C. The length difference between two strings

D. The number of common substrings between two strings

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It counts the smallest number of edits (insertions, deletions, substitutions) needed to convert one string into another.

2. Step 2: Compare options with the definition

   Only The minimum number of single-character edits to change one string into the other correctly describes this minimum edit count concept.

3. Final Answer:

   The minimum number of single-character edits to change one string into the other -> Option A

4. Quick Check:

   Levenshtein distance = minimum edits [OK]

Hint: Think of edits needed to transform one word to another [OK]

Common Mistakes:

• Confusing with longest common subsequence
• Thinking it measures string length difference only
• Assuming it counts matching characters

2. Which Rust code snippet correctly initializes a 2D vector for Levenshtein distance with dimensions (m+1) x (n+1)?

easy

A. let dp = vec![vec![0; m+1]; n+1];

B. let mut dp = vec![vec![0; n+1]; m+1];

C. let mut dp = vec![vec![0; m]; n];

D. let dp = vec![vec![0; n]; m];

Solution

1. Step 1: Identify correct dimensions for DP table

   The DP table for Levenshtein distance has (m+1) rows and (n+1) columns, where m and n are string lengths.

2. Step 2: Match Rust vector initialization syntax

   let mut dp = vec![vec![0; n+1]; m+1]; correctly creates a mutable 2D vector with m+1 rows and n+1 columns filled with zeros.

3. Final Answer:

   let mut dp = vec![vec![0; n+1]; m+1]; -> Option B

4. Quick Check:

   Rows = m+1, Columns = n+1, mutable vector [OK]

Hint: Rows = m+1, columns = n+1 for DP matrix [OK]

Common Mistakes:

• Swapping m and n in dimensions
• Forgetting to add 1 to lengths
• Not making vector mutable

3. What is the output of the following Rust code snippet calculating Levenshtein distance between "kitten" and "sitting"?

fn main() {
    let s1 = "kitten";
    let s2 = "sitting";
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 0..=m {
        dp[i][0] = i;
    }
    for j in 0..=n {
        dp[0][j] = j;
    }

    for i in 1..=m {
        for j in 1..=n {
            if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::cmp::min(
                    dp[i - 1][j - 1],
                    std::cmp::min(dp[i][j - 1], dp[i - 1][j]),
                );
            }
        }
    }
    println!("{}", dp[m][n]);
}

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Understand the strings and DP setup

   Strings are "kitten" (length 6) and "sitting" (length 7). The DP table is correctly initialized and filled using Levenshtein logic.

2. Step 2: Calculate Levenshtein distance manually

   Transform "kitten" to "sitting" requires 3 substitutions and 1 insertion, total 4 edits.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Levenshtein("kitten", "sitting") = 4 [OK]

Hint: Count edits: kitten -> sitten -> sittin -> sitting [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Misindexing string characters
• Off-by-one errors in loops

4. Identify the bug in this Rust code snippet for Levenshtein distance:

for i in 1..m {
    for j in 1..n {
        if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
            dp[i][j] = dp[i - 1][j - 1];
        } else {
            dp[i][j] = 1 + std::cmp::min(
                dp[i - 1][j - 1],
                std::cmp::min(dp[i][j - 1], dp[i - 1][j]),
            );
        }
    }
}

medium

A. Not initializing dp[0][j] and dp[i][0] before loops

B. Indexing s1 and s2 with i and j instead of i-1 and j-1

C. Loop ranges should be 1..=m and 1..=n to include last indices

D. Using std::cmp::max instead of std::cmp::min in calculation

Solution

1. Step 1: Check loop ranges for DP filling

   Loops use 1..m and 1..n which exclude the last index (m and n). They should be inclusive (1..=m and 1..=n) to cover all characters.

2. Step 2: Verify other code parts

   Indexing with i-1 and j-1 is correct, min is used properly, and initialization is assumed done outside snippet.

3. Final Answer:

   Loop ranges should be 1..=m and 1..=n to include last indices -> Option C

4. Quick Check:

   Inclusive loops needed for full DP table [OK]

Hint: Use inclusive ranges 1..=m and 1..=n for full coverage [OK]

Common Mistakes:

• Using exclusive ranges missing last character
• Incorrect indexing causing panic
• Skipping DP initialization

5. Given two strings s1 = "intention" and s2 = "execution", what is the Levenshtein distance computed by the Rust algorithm? Use the standard operations: insert, delete, substitute with cost 1 each.

hard

A. 7

B. 8

C. 5

D. 6

Solution

1. Step 1: Analyze the strings and possible edits

   "intention" (i n t e n t i o n) to "execution" (e x e c u t i o n). Minimal edits: substitute i->e, n->x, t->e, e->c, n->u, plus one insertion or deletion needed, total 6 edits.

2. Step 2: Confirm with Levenshtein algorithm logic

   The DP computes the minimum cost as 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Levenshtein("intention", "execution") = 6 [OK]

Hint: Count minimal edits stepwise between strings [OK]

Common Mistakes:

• Ignoring insertions or deletions
• Miscounting substitutions
• Assuming equal length means zero edits