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

↓

Fill table row by row

↓

Result is dp[m

We build a table comparing prefixes of two strings, filling it step-by-step using insert, delete, and replace costs to find minimum edits.

Execution Sample

DSA C

int min(int a, int b, int c) {
    return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c);
}

int levenshtein(char *s, char *t) {
    int m = strlen(s), n = strlen(t);
    int dp[m+1][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];
}

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

Execution Table

Step	Operation	Cell (i,j)	Characters Compared	DP Value Computed	DP Table State (partial)
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 s[0]='k' and t[0]='s'	(1,1)	'k' vs 's'	1 + min(1,1,0)=1	[[0, 1, 2, 3], [1, 1, _, _], [2, _, _, _], [3, _, _, _]]
9	Compare s[0]='k' and t[1]='i'	(1,2)	'k' vs 'i'	1 + min(2,1,1)=2	[[0, 1, 2, 3], [1, 1, 2, _], [2, _, _, _], [3, _, _, _]]
10	Compare s[0]='k' and t[2]='t'	(1,3)	'k' vs 't'	1 + min(3,2,2)=3	[[0, 1, 2, 3], [1, 1, 2, 3], [2, _, _, _], [3, _, _, _]]
11	Compare s[1]='i' and t[0]='s'	(2,1)	'i' vs 's'	1 + min(1,2,1)=2	[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, _, _], [3, _, _, _]]
12	Compare s[1]='i' and t[1]='i'	(2,2)	'i' vs 'i'	dp[1][1]=1	[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, _], [3, _, _, _]]
13	Compare s[1]='i' and t[2]='t'	(2,3)	'i' vs 't'	1 + min(3,1,2)=2	[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, _, _, _]]
14	Compare s[2]='t' and t[0]='s'	(3,1)	't' vs 's'	1 + min(2,3,2)=3	[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 3, _, _]]
15	Compare s[2]='t' and t[1]='i'	(3,2)	't' vs 'i'	1 + min(1,3,2)=2	[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 3, 2, _]]
16	Compare s[2]='t' and t[2]='t'	(3,3)	't' vs 't'	dp[2][2]=1	[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 3, 2, 1]]
17	End	N/A	N/A	Result dp[3][3]=1	Final DP Table: [[0,1,2,3], [1,1,2,3], [2,2,1,2], [3,3,2,1]]

💡 All cells filled; dp[m][n] = 1 is the minimum edit distance

Variable Tracker

Variable	Start	After Step 5	After Step 10	After Step 15	Final
i	0	1	2	3	3
j	0	0	3	2	3
dp[0][0]	0	0	0	0	0
dp[1][1]	undefined	1	1	1	1
dp[3][3]	undefined	undefined	undefined	undefined	1

Key Moments - 3 Insights

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

Because the first row represents converting an empty string to the prefix of the second string by insertions, and the first column represents converting the prefix of the first string to an empty string by deletions. This is shown in execution_table rows 2-7.

Why do we use dp[i-1][j-1] directly when characters match instead of adding 1?

When characters match, no edit is needed, so the cost remains the same as converting the previous prefixes (dp[i-1][j-1]). This is shown in execution_table row 12 and 16.

How do we decide which operation (insert, delete, replace) to choose when characters differ?

We pick the minimum cost among insert (dp[i][j-1]), delete (dp[i-1][j]), and replace (dp[i-1][j-1]) plus 1. This is shown in execution_table rows 8, 9, 11, 13, 14, and 15.

Visual Quiz - 3 Questions

Look at the execution_table at step 12. What is the dp value computed for cell (2,2)?

A 0

B 2

C 1

D 3

💡 Hint

Check the 'DP Value Computed' column at step 12 in execution_table.

At which step does the condition 'characters equal' first apply in the table filling?

A Step 8

B Step 12

C Step 16

D Step 14

💡 Hint

Look for the first step where dp[i][j] = dp[i-1][j-1] in execution_table.

If the first string was empty, what would be the dp value at cell (0,3)?

A 3

B 0

C 1

D Undefined

💡 Hint

Refer to initialization steps 2-4 in execution_table where first row is filled.

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits to convert one string to another.
Use a DP table dp[m+1][n+1] where m,n are string lengths.
Initialize first row and column with 0..m and 0..n.
Fill dp[i][j]: if chars equal dp[i-1][j-1], else 1 + min(insert, delete, replace).
Result is dp[m][n], the minimum edit distance.

Full Transcript

The Edit Distance Problem (Levenshtein) calculates the minimum number of edits needed to change one string into another. We use a table where rows represent prefixes of the first string and columns represent prefixes of the second string. We start by filling the first row and column with incremental values representing insertions or deletions. Then, for each cell, if the characters match, we copy the diagonal value. If not, we take one plus the minimum of the three possible operations: insert, delete, or replace. The final answer is at the bottom-right cell of the table. This step-by-step filling is shown in the execution table, and variable changes are tracked. Common confusions include why we initialize the first row and column, why matching characters copy the diagonal value, and how we choose the minimum operation cost. The visual quiz tests understanding of these steps.