Edit Distance Problem Levenshtein in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

What is the output of the following Rust code that calculates the Levenshtein distance between two strings?

DSA Rust

fn levenshtein(a: &str, b: &str) -> usize {
    let mut costs = vec![0; b.len() + 1];
    for j in 0..=b.len() {
        costs[j] = j;
    }
    for (i, ca) in a.chars().enumerate() {
        let mut last_cost = i;
        costs[0] = i + 1;
        for (j, cb) in b.chars().enumerate() {
            let new_cost = if ca == cb {
                last_cost
            } else {
                1 + last_cost.min(costs[j]).min(costs[j + 1])
            };
            last_cost = costs[j + 1];
            costs[j + 1] = new_cost;
        }
    }
    costs[b.len()]
}

fn main() {
    let dist = levenshtein("kitten", "sitting");
    println!("{}", dist);
}

A 4

B 5

C 2

D 3

💡 Hint

Think about the minimum number of edits (insertions, deletions, substitutions) to convert 'kitten' to 'sitting'.

The Levenshtein distance between "kitten" and "sitting" is 3. The edits are: substitute 'k' with 's', substitute 'e' with 'i', and insert 'g' at the end.

🧠 Conceptual

intermediate

Understanding Levenshtein Distance Operations

Which of the following operations are considered when calculating the Levenshtein distance between two strings?

A Substitution, Transposition, Reversal

B Insertion, Deletion, Transposition

C Insertion, Deletion, Substitution

D Insertion, Reversal, Duplication

💡 Hint

Levenshtein distance counts the minimum number of single-character edits.

Levenshtein distance counts the minimum number of insertions, deletions, and substitutions needed to change one string into another.

🔧 Debug

advanced

Identify the Error in Levenshtein Distance Implementation

What error will the following Rust code produce when calculating the Levenshtein distance?

DSA Rust

fn levenshtein(a: &str, b: &str) -> usize {
    let mut costs = vec![0; b.len()];
    for j in 0..=b.len() {
        costs[j] = j;
    }
    for (i, ca) in a.chars().enumerate() {
        let mut last_cost = i;
        costs[0] = i + 1;
        for (j, cb) in b.chars().enumerate() {
            let new_cost = if ca == cb {
                last_cost
            } else {
                1 + last_cost.min(costs[j]).min(costs[j + 1])
            };
            last_cost = costs[j + 1];
            costs[j + 1] = new_cost;
        }
    }
    costs[b.len()]
}

fn main() {
    let dist = levenshtein("abc", "yabd");
    println!("{}", dist);
}

A Index out of bounds panic at runtime

B Compilation error due to type mismatch

C Prints incorrect distance value 0

D Runs correctly and prints 2

💡 Hint

Check the size of the vector and the indexing inside the loop.

The vector 'costs' is initialized with length b.len(), but the code accesses costs[b.len()] which is out of bounds, causing a runtime panic.

📝 Syntax

advanced

Correct the Syntax Error in Levenshtein Distance Code

Which option fixes the syntax error in this Rust code snippet for Levenshtein distance?

DSA Rust

let new_cost = if ca == cb {
    last_cost
} else
    1 + last_cost.min(costs[j]).min(costs[j + 1])
};

A Replace 'if' with 'match' expression

B Add braces around else block: else { 1 + last_cost.min(costs[j]).min(costs[j + 1]) }

C Remove the semicolon at the end of the else expression

D Change 'let' to 'var' for new_cost declaration

💡 Hint

In Rust, multi-line else blocks need braces.

The else block spans multiple lines and must be enclosed in braces to be syntactically correct.

🚀 Application

expert

Minimum Edit Distance for Real-World Spell Correction

Given the words "intention" and "execution", what is the Levenshtein distance calculated by the Rust function below?

DSA Rust

fn levenshtein(a: &str, b: &str) -> usize {
    let mut costs = vec![0; b.len() + 1];
    for j in 0..=b.len() {
        costs[j] = j;
    }
    for (i, ca) in a.chars().enumerate() {
        let mut last_cost = i;
        costs[0] = i + 1;
        for (j, cb) in b.chars().enumerate() {
            let new_cost = if ca == cb {
                last_cost
            } else {
                1 + last_cost.min(costs[j]).min(costs[j + 1])
            };
            last_cost = costs[j + 1];
            costs[j + 1] = new_cost;
        }
    }
    costs[b.len()]
}

fn main() {
    let dist = levenshtein("intention", "execution");
    println!("{}", dist);
}

A 5

B 6

C 4

D 7

💡 Hint

Count the minimum edits: substitutions, insertions, deletions to convert "intention" to "execution".

The Levenshtein distance between "intention" and "execution" is 5, representing the minimum edits needed.

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