Edit Distance Problem Levenshtein in DSA Rust - Execution Trace

Concept Flow - Edit Distance Problem Levenshtein

Start with empty DP table

↓

Fill first row and column

↓

For each cell dp[i

↓

Compare chars s1[i-1

↓

If equal: dp[i

↓

If different: dp[i

↓

Repeat for all i,j

↓

Result at dp[m

We build a table where each cell shows the minimum edits to convert prefixes of the two strings, filling row by row comparing characters.

Execution Sample

DSA Rust

fn levenshtein(s1: &str, s2: &str) -> usize {
    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 + dp[i-1][j-1].min(dp[i][j-1].min(dp[i-1][j]));
            }
        }
    }
    dp[m][n]
}

This code calculates the minimum number of edits (insert, delete, replace) to convert s1 into s2 using a DP table.

Execution Table

Step	Operation	Cell (i,j)	Chars Compared	DP Value Computed	DP Table Visual
Init	Set dp[i][0] = i	(0,0)	-	0	[0, _, _, _] [1, _, _, _] [2, _, _, _] [3, _, _, _]
Init	Set dp[0][j] = j	(0,1)	-	1	[0, 1, 2, 3] [1, _, _, _] [2, _, _, _] [3, _, _, _]
Init	Set dp[0][j] = j	(0,2)	-	2	[0, 1, 2, 3] [1, _, _, _] [2, _, _, _] [3, _, _, _]
Init	Set dp[0][j] = j	(0,3)	-	3	[0, 1, 2, 3] [1, _, _, _] [2, _, _, _] [3, _, _, _]
Fill	Compare s1[0]='k' and s2[0]='s'	(1,1)	'k' vs 's'	1	[0, 1, 2, 3] [1, 1, _, _] [2, _, _, _] [3, _, _, _]
Fill	Compare s1[0]='k' and s2[1]='i'	(1,2)	'k' vs 'i'	2	[0, 1, 2, 3] [1, 1, 2, _] [2, _, _, _] [3, _, _, _]
Fill	Compare s1[0]='k' and s2[2]='t'	(1,3)	'k' vs 't'	3	[0, 1, 2, 3] [1, 1, 2, 3] [2, _, _, _] [3, _, _, _]
Fill	Compare s1[1]='i' and s2[0]='s'	(2,1)	'i' vs 's'	2	[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, _, _] [3, _, _, _]
Fill	Compare s1[1]='i' and s2[1]='i'	(2,2)	'i' vs 'i'	1	[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, 1, _] [3, _, _, _]
Fill	Compare s1[1]='i' and s2[2]='t'	(2,3)	'i' vs 't'	2	[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, 1, 2] [3, _, _, _]
Fill	Compare s1[2]='t' and s2[0]='s'	(3,1)	't' vs 's'	3	[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, 1, 2] [3, 3, _, _]
Fill	Compare s1[2]='t' and s2[1]='i'	(3,2)	't' vs 'i'	2	[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, 1, 2] [3, 3, 2, _]
Fill	Compare s1[2]='t' and s2[2]='t'	(3,3)	't' vs 't'	1	[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, 1, 2] [3, 3, 2, 1]
End	Result dp[m][n]	(3,3)	-	1	Final edit distance is 1

💡 All cells filled; dp[m][n] holds minimum edit distance

Variable Tracker

Variable	Start	After Step 5	After Step 9	After Step 12	Final
dp[0][0]	0	0	0	0	0
dp[1][1]	0	1	1	1	1
dp[2][2]	0	0	1	1	1
dp[3][3]	0	0	0	0	1
i	0	1	2	3	3
j	0	1	2	2	3

Key Moments - 3 Insights

Why do we initialize the first row and column of the DP table with increasing numbers?

Because converting an empty string to a string of length j requires j insertions, and converting a string of length i to empty requires i deletions. This is shown in the initialization steps in the execution_table rows 1-4.

Why do we take the minimum of three values when characters differ?

We consider three operations: insert, delete, and replace. The minimum cost among these plus one is the best choice. This is shown in execution_table rows 5-12 where dp[i][j] is computed as 1 + min of neighbors.

Why does the DP value stay the same when characters match?

If characters are equal, no edit is needed, so dp[i][j] equals dp[i-1][j-1]. This is shown in execution_table rows 9 and 12 where characters match and dp value copies the diagonal.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the dp value computed for cell (2,2)?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'DP Value Computed' column for step 9 in execution_table.

At which step does the condition s1[i-1] == s2[j-1] become true for the first time?

A Step 5

B Step 9

C Step 12

D Step 3

💡 Hint

Look at the 'Chars Compared' and 'Operation' columns in execution_table to find first equality.

If the first character of s1 was the same as s2, how would the dp value at (1,1) change?

A It would be 0

B It would be 1

C It would be 2

D It would be 3

💡 Hint

Refer to variable_tracker and execution_table step 5 where dp[1][1] is computed based on character equality.

Concept Snapshot

Edit Distance (Levenshtein) uses a DP table dp[m+1][n+1].
Initialize dp[i][0] = i and dp[0][j] = j.
For each dp[i][j], if chars equal: dp[i][j] = dp[i-1][j-1].
Else dp[i][j] = 1 + min(insert dp[i][j-1], delete dp[i-1][j], replace dp[i-1][j-1]).
Result is dp[m][n], minimum edits to convert s1 to s2.

Full Transcript

The Levenshtein edit distance problem calculates the minimum number of edits needed to change one string into another. We use a two-dimensional table dp where dp[i][j] represents the minimum edits to convert the first i characters of s1 into the first j characters of s2. We start by filling the first row and column with incremental values representing conversions from or to empty strings. Then, for each cell, we compare the characters of s1 and s2 at positions i-1 and j-1. If they match, no new edit is needed, so dp[i][j] equals dp[i-1][j-1]. If they differ, we consider the cost of insertion, deletion, and replacement, taking the minimum plus one. This process continues until the entire table is filled. The final answer is found at dp[m][n], representing the minimum edits for the full strings. This step-by-step filling is shown in the execution table, with the DP table state updated at each step. Key points include the initialization of the first row and column, the handling of character matches, and the choice among three operations when characters differ.

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