Edit Distance Problem Levenshtein in DSA C# - Execution Trace

Concept Flow - Edit Distance Problem Levenshtein

Start with two strings

↓

Create DP table with size (m+1)x(n+1)

↓

Initialize first row and column

↓

For each cell dp[i

↓

If chars equal: dp[i

↓

Else: dp[i

↓

Final answer at dp[m

Build a table comparing prefixes of two strings, filling it with minimum edits needed step-by-step.

Execution Sample

DSA C#

string s1 = "cat";
string s2 = "cut";
int[,] dp = new int[4,4];
// Fill dp table
// dp[m,n] = edit distance

Calculate minimum edits to convert "cat" to "cut" using a table.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table State
1	Initialize dp[0][0]	(0,0)	N/A	0	[[0,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]
2	Initialize first row	(0,1)	N/A	1	[[0,1,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]
3	Initialize first row	(0,2)	N/A	2	[[0,1,2,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]
4	Initialize first row	(0,3)	N/A	3	[[0,1,2,3],[_,_,_,_],[_,_,_,_],[_,_,_,_]]
5	Initialize first column	(1,0)	N/A	1	[[0,1,2,3],[1,_,_,_],[_,_,_,_],[_,_,_,_]]
6	Initialize first column	(2,0)	N/A	2	[[0,1,2,3],[1,_,_,_],[2,_,_,_],[_,_,_,_]]
7	Initialize first column	(3,0)	N/A	3	[[0,1,2,3],[1,_,_,_],[2,_,_,_],[3,_,_,_]]
8	Compare s1[1]='c' and s2[1]='c'	(1,1)	'c' vs 'c'	0	[[0,1,2,3],[1,0,_,_],[2,_,_,_],[3,_,_,_]]
9	Compare s1[1]='c' and s2[2]='u'	(1,2)	'c' vs 'u'	1	[[0,1,2,3],[1,0,1,_],[2,_,_,_],[3,_,_,_]]
10	Compare s1[1]='c' and s2[3]='t'	(1,3)	'c' vs 't'	2	[[0,1,2,3],[1,0,1,2],[2,_,_,_],[3,_,_,_]]
11	Compare s1[2]='a' and s2[1]='c'	(2,1)	'a' vs 'c'	1	[[0,1,2,3],[1,0,1,2],[2,1,_,_],[3,_,_,_]]
12	Compare s1[2]='a' and s2[2]='u'	(2,2)	'a' vs 'u'	1	[[0,1,2,3],[1,0,1,2],[2,1,1,_],[3,_,_,_]]
13	Compare s1[2]='a' and s2[3]='t'	(2,3)	'a' vs 't'	2	[[0,1,2,3],[1,0,1,2],[2,1,1,2],[3,_,_,_]]
14	Compare s1[3]='t' and s2[1]='c'	(3,1)	't' vs 'c'	2	[[0,1,2,3],[1,0,1,2],[2,1,1,2],[3,2,_,_]]
15	Compare s1[3]='t' and s2[2]='u'	(3,2)	't' vs 'u'	2	[[0,1,2,3],[1,0,1,2],[2,1,1,2],[3,2,2,_]]
16	Compare s1[3]='t' and s2[3]='t'	(3,3)	't' vs 't'	1	[[0,1,2,3],[1,0,1,2],[2,1,1,2],[3,2,2,1]]

💡 Completed filling dp table; dp[3][3] = 1 is the minimum edit distance

Variable Tracker

Variable	Start	After Step 8	After Step 12	After Step 16
dp[0][0]	0	0	0	0
dp[1][1]	undefined	0	0	0
dp[2][2]	undefined	undefined	1	1
dp[3][3]	undefined	undefined	undefined	1

Key Moments - 3 Insights

Why do we initialize the first row and column of the dp table?

Because they represent converting an empty string to a prefix of the other string, so the cost is the length of that prefix (see steps 2-7 in execution_table).

Why is dp[i][j] set to dp[i-1][j-1] when characters match?

Because no edit is needed if characters are the same, so the cost stays the same as for the smaller prefixes (see step 8 and 16).

How do we decide the minimum edit when characters differ?

We take 1 plus the minimum of insert, delete, or replace operations from neighboring cells (see steps 9, 11, 12).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the dp cell value for dp[1][1]?

A 0

B 1

C 2

D undefined

💡 Hint

Check the 'DP Cell Value' column at step 8 in execution_table.

At which step does the dp cell dp[3][3] get its final value?

A Step 14

B Step 15

C Step 16

D Step 13

💡 Hint

Look for dp[3][3] updates in the 'Indices (i,j)' column in execution_table.

If the characters at s1[2] and s2[2] were equal, how would dp[2][2] change at step 12?

A It would be 0

B It would be 1

C It would be same as dp[1][1]

D It would be 2

💡 Hint

Refer to the rule in key_moments about matching characters and dp[i][j] value.

Concept Snapshot

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

Full Transcript

The Edit Distance Problem calculates the minimum number of edits to change one string into another. We use a table dp where dp[i][j] means the minimum edits to convert the first i characters of string s1 to the first j characters of string s2. We start by initializing the first row and column because converting from or to an empty string requires as many insertions or deletions as the length of the other string. Then, for each cell, if the characters match, we copy the diagonal value since no edit is needed. If they differ, we take one plus the minimum of three possible edits: insert, delete, or replace. The final answer is at dp[m][n]. This step-by-step filling of the table helps visualize how the solution builds up from smaller subproblems.

Practice

1. What does the Levenshtein Edit Distance between two strings measure?

easy

A. The total length of both strings combined

B. The maximum length of common substring between two strings

C. The number of characters that are the same in both strings

D. The minimum number of single-character edits to change one string into another

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It counts the minimum edits (insertions, deletions, substitutions) to convert one string into another.

2. Step 2: Compare with other options

   Options B and C describe different string metrics, not edit distance.

3. Final Answer:

   The minimum number of single-character edits to change one string into another -> Option D

4. Quick Check:

   Edit distance = minimum edits [OK]

Hint: Edit distance counts minimal edits to match strings [OK]

Common Mistakes:

• Confusing edit distance with longest common substring
• Thinking it counts only substitutions
• Assuming it measures string length

2. Which of the following C# method signatures correctly represents a function to compute Levenshtein distance between two strings s1 and s2?

easy

A. private string LevenshteinDistance(string s1, string s2)

B. public void LevenshteinDistance(int s1, int s2)

C. public int LevenshteinDistance(string s1, string s2)

D. public int LevenshteinDistance(int[] s1, int[] s2)

Solution

1. Step 1: Check parameter types for string inputs

   The function should accept two strings, so parameters must be string types.

2. Step 2: Check return type for distance value

   Distance is an integer, so return type should be int, not void or string.

3. Final Answer:

   public int LevenshteinDistance(string s1, string s2) -> Option C

4. Quick Check:

   Function signature matches string inputs and int output [OK]

Hint: Function takes strings, returns int distance [OK]

Common Mistakes:

• Using void return type instead of int
• Using int parameters instead of strings
• Returning string instead of int

3. What is the output of the following C# code snippet?

var s1 = "kitten";
var s2 = "sitting";
Console.WriteLine(LevenshteinDistance(s1, s2));

int LevenshteinDistance(string a, string b) {
    int[,] dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 0; i <= a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j <= b.Length; j++) dp[0, j] = j;
    for (int i = 1; i <= a.Length; i++) {
        for (int j = 1; j <= b.Length; j++) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + cost);
        }
    }
    return dp[a.Length, b.Length];
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions, insertions, deletions.

2. Step 2: Calculate Levenshtein distance manually

   Changes: k->s (substitution), e->i (substitution), t->t (no change), t->t (no change), e->i (substitution), n->n (no change), add g (insertion) = 3 substitutions + 1 insertion = 4 edits total.

3. Final Answer:

   4 -> Option B

4. Quick Check:

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

Hint: Remember common example: kitten -> sitting = 4 edits [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Miscounting character positions
• Confusing with Hamming distance

4. Identify the bug in this Levenshtein distance C# code snippet:

int LevenshteinDistance(string a, string b) {
    int[,] dp = new int[a.Length, b.Length];
    for (int i = 0; i < a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j < b.Length; j++) dp[0, j] = j;
    for (int i = 1; i < a.Length; i++) {
        for (int j = 1; j < b.Length; j++) {
            int cost = (a[i] == b[j]) ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + cost);
        }
    }
    return dp[a.Length - 1, b.Length - 1];
}

medium

A. Array size should be (a.Length+1, b.Length+1) and loops adjusted

B. Cost calculation should use a[i-1] and b[j-1]

C. Return statement should be dp[a.Length, b.Length]

D. No bug, code is correct

Solution

1. Step 1: Check array size and indexing

   dp array must be sized (a.Length+1, b.Length+1) to include empty prefixes; current size misses last row/column.

2. Step 2: Adjust loops to run from 0 to length inclusive

   Loops should run to <= length to fill dp correctly; current loops miss last indices.

3. Final Answer:

   Array size should be (a.Length+1, b.Length+1) and loops adjusted -> Option A

4. Quick Check:

   dp array size must include empty string row/column [OK]

Hint: dp array must be one larger than string lengths [OK]

Common Mistakes:

• Using array size equal to string length only
• Incorrect loop bounds causing index errors
• Ignoring empty string base cases

5. Given two strings s1 = "intention" and s2 = "execution", what is the Levenshtein distance between them? Use the standard operations: insert, delete, substitute.

hard

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Analyze differences between "intention" and "execution"

   Compare characters and count minimal edits: substitutions and insertions/deletions.

2. Step 2: Calculate minimal edits manually

   Edits: i->e (substitution), n->x (substitution), t->c (substitution), insert u, substitute n->o, substitute n->n (no change), total 5 edits.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Distance("intention", "execution") = 5 [OK]

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing with Hamming distance