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

↓

Compare chars s1[i-1

↓

i

↓

i

↓

i-1

↓

i

↓

i-1

↓

Result is dp[m

This flow shows how we build a table to find the minimum edits to change one string into another by comparing characters and choosing the best operation.

Execution Sample

DSA C++

string s1 = "cat";
string s2 = "cut";
int dp[4][4];
// Fill dp table for edit distance
// dp[i][j] = min edits to convert s1[0..i-1] to s2[0..j-1]

This code sets up a table to find the minimum edits to convert "cat" into "cut".

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table State
1	Initialize dp[0][j]	(0,0)	-	0	[[0,1,2,3], [ , , , ], [ , , , ], [ , , , ]]
2	Initialize dp[0][j]	(0,1)	-	1	[[0,1,2,3], [ , , , ], [ , , , ], [ , , , ]]
3	Initialize dp[0][j]	(0,2)	-	2	[[0,1,2,3], [ , , , ], [ , , , ], [ , , , ]]
4	Initialize dp[0][j]	(0,3)	-	3	[[0,1,2,3], [ , , , ], [ , , , ], [ , , , ]]
5	Initialize dp[i][0]	(1,0)	-	1	[[0,1,2,3], [1, , , ], [ , , , ], [ , , , ]]
6	Initialize dp[i][0]	(2,0)	-	2	[[0,1,2,3], [1, , , ], [2, , , ], [ , , , ]]
7	Initialize dp[i][0]	(3,0)	-	3	[[0,1,2,3], [1, , , ], [2, , , ], [3, , , ]]
8	Compare s1[0]='c' and s2[0]='c'	(1,1)	c vs c	0	[[0,1,2,3], [1,0, , ], [2, , , ], [3, , , ]]
9	Compare s1[0]='c' and s2[1]='u'	(1,2)	c vs u	1	[[0,1,2,3], [1,0,1, ], [2, , , ], [3, , , ]]
10	Compare s1[0]='c' and s2[2]='t'	(1,3)	c vs t	2	[[0,1,2,3], [1,0,1,2], [2, , , ], [3, , , ]]
11	Compare s1[1]='a' and s2[0]='c'	(2,1)	a vs c	1	[[0,1,2,3], [1,0,1,2], [2,1, , ], [3, , , ]]
12	Compare s1[1]='a' and s2[1]='u'	(2,2)	a vs u	1	[[0,1,2,3], [1,0,1,2], [2,1,1, ], [3, , , ]]
13	Compare s1[1]='a' and s2[2]='t'	(2,3)	a vs t	2	[[0,1,2,3], [1,0,1,2], [2,1,1,2], [3, , , ]]
14	Compare s1[2]='t' and s2[0]='c'	(3,1)	t vs c	2	[[0,1,2,3], [1,0,1,2], [2,1,1,2], [3,2, , ]]
15	Compare s1[2]='t' and s2[1]='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[2]='t' and s2[2]='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 1-4	After Step 5-7	After Step 8-10	After Step 11-13	After Step 14-16	Final
dp Table	empty	[[0,1,2,3], [ , , , ], [ , , , ], [ , , , ]]	[[0,1,2,3], [1, , , ], [2, , , ], [3, , , ]]	[[0,1,2,3], [1,0,1,2], [2, , , ], [3, , , ]]	[[0,1,2,3], [1,0,1,2], [2,1,1,2], [3, , , ]]	[[0,1,2,3], [1,0,1,2], [2,1,1,2], [3,2,2,1]]	[[0,1,2,3], [1,0,1,2], [2,1,1,2], [3,2,2,1]]

Key Moments - 3 Insights

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

The first row and column represent converting an empty string to the other string by only insertions or deletions. This sets the base cases for the rest of the table, as shown in steps 1-7 of the execution_table.

Why does dp[i][j] equal dp[i-1][j-1] when characters match?

When characters are the same, no edit is needed for that position, so the cost remains the same as converting the previous substrings, as seen in step 8 and step 16.

Why do we take the minimum of three operations plus one when characters differ?

Because we can insert, delete, or replace a character, and we want the least costly option. This is shown in steps like 9, 11, and 12 where dp[i][j] is 1 plus the minimum of neighboring cells.

Visual Quiz - 3 Questions

Look at the execution_table at step 8. What is the dp cell value for dp[1][1] when comparing 'c' and 'c'?

A 0

B 1

C 2

D Undefined

💡 Hint

Refer to the 'DP Cell Value' column in execution_table row with Step 8.

At which step does the dp table first show a value of 2 in the last column of the second row?

A Step 13

B Step 10

C Step 16

D Step 7

💡 Hint

Check the 'DP Table State' column for the second row after each step.

If the characters at s1[i-1] and s2[j-1] are the same, how does dp[i][j] relate to dp[i-1][j-1]?

A dp[i][j] = min of dp[i-1][j] and dp[i][j-1]

B dp[i][j] = dp[i-1][j-1] + 1

C dp[i][j] = dp[i-1][j-1]

D dp[i][j] = max of dp[i-1][j] and dp[i][j-1]

💡 Hint

See steps 8 and 16 in execution_table where characters match.

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits (insert, delete, replace) to convert one string to another.
Use a DP table dp[m+1][n+1] where dp[i][j] = min edits for s1[0..i-1] to s2[0..j-1].
Initialize first row and column for empty string conversions.
If chars match: dp[i][j] = dp[i-1][j-1]. Else dp[i][j] = 1 + min(delete, insert, replace).
Result is dp[m][n].

Full Transcript

The Edit Distance Problem, also called Levenshtein distance, calculates the minimum number of edits needed to change one string into another. We use a table to store results for substrings. The table size is (length of first string + 1) by (length of second string + 1). We fill the first row and column with incremental values representing converting empty strings. For each cell, if the characters are the same, we copy the diagonal value. If different, we take one plus the minimum of the left, top, and diagonal cells representing insert, delete, and replace operations. The final answer is at the bottom-right cell of the table. This method ensures we consider all possible edits efficiently.

Practice

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

easy

A. The minimum number of insertions, deletions, or substitutions to convert one string into another

B. The number of matching characters in the same positions

C. The length difference between two strings

D. The maximum number of characters that differ between two strings

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes are needed to make two strings equal.

2. Step 2: Identify allowed operations

   Allowed operations are insertion, deletion, and substitution of characters.

3. Final Answer:

   The minimum number of insertions, deletions, or substitutions to convert one string into another -> Option A

4. Quick Check:

   Edit Distance = minimum edits needed [OK]

Hint: Think of edits needed to match strings exactly [OK]

Common Mistakes:

• Confusing edit distance with matching characters count
• Ignoring substitution as an allowed operation
• Thinking it measures only length difference

2. Which of the following is the correct way to initialize the base case for the DP table in Levenshtein distance calculation in C++?

easy

A. for (int i = 0; i <= m; i++) dp[i][0] = i;

B. for (int j = 0; j <= n; j++) dp[0][j] = 0;

C. dp[0][0] = 1;

D. for (int i = 1; i <= m; i++) dp[i][0] = 0;

Solution

1. Step 1: Understand base case meaning

   dp[i][0] means converting first i characters of string1 to empty string, so requires i deletions.

2. Step 2: Identify correct initialization

   Setting dp[i][0] = i correctly counts deletions needed for empty second string.

3. Final Answer:

   for (int i = 0; i <= m; i++) dp[i][0] = i; -> Option A

4. Quick Check:

   Base case rows = index count [OK]

Hint: Base case dp[i][0] = i for deletions [OK]

Common Mistakes:

• Initializing dp[0][j] incorrectly to zero
• Starting loops from 1 instead of 0
• Setting dp[0][0] to 1 instead of 0

3. What is the output of the following C++ code snippet that calculates the Levenshtein distance between "kitten" and "sitting"?

int levenshteinDistance(const string &s, const string &t) {
    int m = s.size(), n = t.size();
    vector dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }
    return dp[m][n];
}

cout << levenshteinDistance("kitten", "sitting") << endl;

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions and insertions.

2. Step 2: Calculate minimum edits

   Substitute 'k'->'s', substitute 'e'->'i', insert 'g' at end, total 3 edits.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Levenshtein distance("kitten", "sitting") = 3 [OK]

Hint: Count substitutions + insertions needed [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Misaligning indices causing off-by-one errors
• Confusing Levenshtein with Hamming distance

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

int levenshteinDistance(string s, string t) {
    int m = s.size(), n = t.size();
    vector dp(m, vector<int>(n));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }
    return dp[m][n];
}

medium

A. The return statement should be dp[m-1][n-1]

B. The dp vector is initialized with size m x n instead of (m+1) x (n+1)

C. The loops should start from 0 instead of 1

D. The comparison s[i] == t[j] is incorrect

Solution

1. Step 1: Check dp vector initialization

   dp must have size (m+1) x (n+1) to include base cases for empty strings.

2. Step 2: Identify impact of wrong size

   With size m x n, accessing dp[m][0] or dp[0][n] causes out-of-bounds errors.

3. Final Answer:

   The dp vector is initialized with size m x n instead of (m+1) x (n+1) -> Option B

4. Quick Check:

   dp size must be (m+1) x (n+1) [OK]

Hint: dp size must cover empty string cases [OK]

Common Mistakes:

• Forgetting to add +1 to dp dimensions
• Returning dp[m][n] without proper dp size
• Incorrect loop ranges causing index errors

5. Given two strings "intention" and "execution", what is the minimum edit distance using Levenshtein algorithm? Show the reasoning for each step.

hard

A. 7

B. 5

C. 6

D. 8

Solution

1. Step 1: Analyze character differences

   Compare "intention" and "execution" character by character, counting edits needed.

2. Step 2: Calculate minimal edits

   The optimal alignment requires 6 edits: substitutions, insertions, and deletions to match exactly.

3. Final Answer:

   6 -> Option C

4. Quick Check:

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

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Ignoring insertions or deletions
• Miscounting substitutions
• Assuming only substitutions needed