Edit Distance Problem Levenshtein in DSA Typescript - 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 (i,j):

↓

Compare characters s1[i-1

↓

Copy diagonal

↓

Fill table row by row

↓

Result at dp[m

We build a table to find the minimum edits to convert one string to another by comparing characters and choosing the best operation step by step.

Execution Sample

DSA Typescript

const s1 = "kitten";
const s2 = "sitting";
// dp[i][j] = edit distance between s1[0..i-1] and s2[0..j-1]

This code calculates the minimum edits to change 'kitten' into 'sitting' using a table.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table Snapshot
1	Initialize dp[0][0]	(0,0)	N/A	0	[[0]]
2	Initialize first row	(0,j)	N/A	j	[[0,1,2,3,4,5,6,7]]
3	Initialize first column	(i,0)	N/A	i	[[0],[1],[2],[3],[4],[5],[6]]
4	Compare 'k' and 's'	(1,1)	'k' vs 's'	1	[[0,1,2,3,4,5,6,7],[1,1]]
5	Compare 'k' and 'i'	(1,2)	'k' vs 'i'	2	[...,[1,1,2]]
6	Compare 'k' and 't'	(1,3)	'k' vs 't'	3	[...,[1,1,2,3]]
7	Compare 'k' and 't'	(1,4)	'k' vs 't'	4	[...,[1,1,2,3,4]]
8	Compare 'k' and 'i'	(1,5)	'k' vs 'i'	5	[...,[1,1,2,3,4,5]]
9	Compare 'k' and 'n'	(1,6)	'k' vs 'n'	6	[...,[1,1,2,3,4,5,6]]
10	Compare 'k' and 'g'	(1,7)	'k' vs 'g'	7	[...,[1,1,2,3,4,5,6,7]]
11	Compare 'i' and 's'	(2,1)	'i' vs 's'	2	[...,[2,2]]
12	Compare 'i' and 'i'	(2,2)	'i' vs 'i'	1	[...,[2,1]]
13	Compare 'i' and 't'	(2,3)	'i' vs 't'	2	[...,[2,1,2]]
14	Compare 'i' and 't'	(2,4)	'i' vs 't'	3	[...,[2,1,2,3]]
15	Compare 'i' and 'i'	(2,5)	'i' vs 'i'	4	[...,[2,1,2,3,4]]
16	Compare 'i' and 'n'	(2,6)	'i' vs 'n'	5	[...,[2,1,2,3,4,5]]
17	Compare 'i' and 'g'	(2,7)	'i' vs 'g'	6	[...,[2,1,2,3,4,5,6]]
...	...	...	...	...	...
Last	Final result	(6,7)	N/A	3	Full dp table with dp[6][7] = 3

💡 All dp cells filled; dp[m][n] = 3 means minimum 3 edits needed

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 10	After Step 17	Final
dp	Empty	First row filled with 0..7	First column filled with 0..6	Partial table filled up to row 1	Partial table filled up to row 2	Full table filled with final value 3 at dp[6][7]
i	0	0	1	1	2	6
j	0	1	0	7	7	7
Current chars	N/A	N/A	'k' vs 's'	'k' vs 'g'	'i' vs 'g'	N/A

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 a prefix of the other string, so the cost is just the length of that prefix (all insertions or deletions). See steps 2 and 3 in the execution_table.

Why do we take the minimum of insert, delete, and replace plus one when characters differ?

Because each operation costs 1, and we want the minimal total edits. We check all three options and pick the smallest. This is shown in steps like 4 and 12 where characters differ or match.

Why does dp[m][n] give the final edit distance?

Because dp[i][j] stores the minimum edits to convert s1[0..i-1] to s2[0..j-1]. So dp[m][n] covers the full strings. See the last step in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the dp cell value for dp[1][1] comparing 'k' and 's'?

A 1

B 0

C 2

D Undefined

💡 Hint

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

At which step does the dp table first show a character match with value copied from diagonal?

A Step 4

B Step 2

C Step 12

D Step 17

💡 Hint

Look for steps where characters compared are equal and dp cell value is less than neighbors, see step 12.

If we changed s2 from 'sitting' to 'kitten', what would happen to dp[6][7] in the final table?

A It would stay 3

B It would be 0

C It would increase

D It would be undefined

💡 Hint

If both strings are identical, edit distance is zero, so dp[m][n] = 0.

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits to convert one string to another.
Use a 2D dp table of size (m+1)x(n+1).
Initialize first row and column with 0..length.
Fill dp[i][j] by comparing chars:
  if equal: dp[i][j] = dp[i-1][j-1]
  else: dp[i][j] = 1 + min(insert, delete, replace)
Result at dp[m][n].

Full Transcript

The Edit Distance Problem (Levenshtein) calculates the minimum number of edits needed to change one string into another. We use a two-dimensional table where each cell dp[i][j] represents the minimum edits to convert the first i characters of the first string to the first j characters of the second string. We start by initializing the first row and column because converting from or to an empty string requires insertions or deletions equal to the length of the other string. Then, for each cell, we compare the characters of the two strings. If they match, we copy the diagonal value. If not, we take the minimum of the three possible operations (insert, delete, replace) plus one. After filling the table, the bottom-right cell gives the final minimum edit distance. This method ensures we consider all possible ways to transform one string into another efficiently.