Edit Distance Problem Levenshtein in DSA Javascript - 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 characters s1[i-1

↓

Copy dp[i-1

↓

Fill dp[i

↓

Repeat until dp[m

↓

Result is dp[m

The flow shows building a table to find minimum edits to convert one string to another by comparing characters and choosing insert, delete, or replace operations.

Execution Sample

DSA Javascript

const s1 = 'kitten';
const s2 = 'sitting';
// dp table size 7x8
// dp[i][j] = min edits for s1[0..i-1] to s2[0..j-1]

This code sets up two strings and a DP table to compute the Levenshtein distance step-by-step.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table State (partial)
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,7], [1, _, _, _, _, _, _, _], [2, _, _, _, _, _, _, _], [3, _, _, _, _, _, _, _], [4, _, _, _, _, _, _, _], [5, _, _, _, _, _, _, _], [6, _, _, _, _, _, _, _]]
4	Compare s1[0]='k' and s2[0]='s'	(1,1)	'k' vs 's'	1	[[0,1,2,3,4,5,6,7], [1,1, _, _, _, _, _, _], ...]
5	Compare s1[1]='i' and s2[1]='i'	(2,2)	'i' vs 'i'	1	[[0,1,2,3,4,5,6,7], [1,1,2, _, _, _, _, _], [2,2,1, _, _, _, _, _], ...]
6	Compare s1[2]='t' and s2[2]='t'	(3,3)	't' vs 't'	1	[[0,1,2,3,4,5,6,7], [1,1,2,3, _, _, _, _], [2,2,1,2, _, _, _, _], [3,3,2,1, _, _, _, _], ...]
7	Compare s1[3]='t' and s2[3]='t'	(4,4)	't' vs 't'	1	[[0,1,2,3,4,5,6,7], [1,1,2,3,4, _, _, _], [2,2,1,2,3, _, _, _], [3,3,2,1,2, _, _, _], [4,4,3,2,1, _, _, _], ...]
8	Compare s1[4]='e' and s2[4]='i'	(5,5)	'e' vs 'i'	2	[[0,1,2,3,4,5,6,7], [1,1,2,3,4,5, _, _], [2,2,1,2,3,4, _, _], [3,3,2,1,2,3, _, _], [4,4,3,2,1,2, _, _], [5,5,4,3,2,2, _, _], ...]
9	Compare s1[5]='n' and s2[5]='n'	(6,6)	'n' vs 'n'	2	[[0,1,2,3,4,5,6,7], [1,1,2,3,4,5,6, _], [2,2,1,2,3,4,5, _], [3,3,2,1,2,3,4, _], [4,4,3,2,1,2,3, _], [5,5,4,3,2,2,3, _], [6,6,5,4,3,3,2, _]]
10	Compare s1[5]='n' and s2[6]='g'	(6,7)	'n' vs 'g'	3	[[0,1,2,3,4,5,6,7], [1,1,2,3,4,5,6,7], [2,2,1,2,3,4,5,6], [3,3,2,1,2,3,4,5], [4,4,3,2,1,2,3,4], [5,5,4,3,2,2,3,4], [6,6,5,4,3,3,2,3]]

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 9	Final
dp[0][0]	undefined	0	0	0	0	0
dp[0][j]	undefined	[0,1,2,3,4,5,6,7]	[0,1,2,3,4,5,6,7]	[0,1,2,3,4,5,6,7]	[0,1,2,3,4,5,6,7]	[0,1,2,3,4,5,6,7]
dp[i][0]	undefined	undefined	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]	[0,1,2,3,4,5,6]
dp[1][1]	undefined	undefined	1	1	1	1
dp[2][2]	undefined	undefined	undefined	1	1	1
dp[3][3]	undefined	undefined	undefined	1	1	1
dp[6][7]	undefined	undefined	undefined	undefined	undefined	3

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 empty strings to prefixes of the other string, so their values are the number of insertions or deletions needed. This is shown in steps 2 and 3 of the execution_table.

Why do we add 1 when characters don't match?

When characters differ, we consider the minimum edits from insert, delete, or replace plus one operation. This is shown in step 4 where dp[1][1] is set to 1 because 'k' != 's'.

Why is dp[m][n] the final answer?

dp[m][n] holds the minimum edits to convert the entire first string to the entire second string, as the table builds solutions from smaller prefixes to full strings, shown in step 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the dp cell value for dp[1][1] and why?

A 1 because characters differ and one edit is needed

B 0 because characters match

C 2 because two edits are needed

D Undefined because not initialized

💡 Hint

Check step 4 in execution_table where 'k' vs 's' differ and dp[1][1] is set to 1

At which step does the dp table first show a value of 2 for any cell?

A Step 3

B Step 5

C Step 8

D Step 9

💡 Hint

Look at dp values in step 8 and see dp[5][5] = 2

If the first string was empty, how would the dp table's first row and column change?

A First row would be increasing numbers, first column would be zeros

B Both first row and column would be increasing numbers

C Both first row and column would be zeros

D First row would be zeros, first column would be increasing numbers

💡 Hint

Refer to variable_tracker rows for dp[0][j] and dp[i][0] initialization

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits (insert, delete, replace) to convert one string to another.
Use a DP table dp of size (m+1)x(n+1).
Initialize dp first row and column with 0..length values.
Fill dp[i][j] by comparing characters:
If match: dp[i][j] = dp[i-1][j-1]
Else: dp[i][j] = 1 + min(insert, delete, replace)
Result is 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 table dp where dp[i][j] represents the minimum edits to convert the first i characters of string one to the first j characters of string two. We start by initializing the first row and column to represent converting empty strings. 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 insert, delete, or replace operations plus one. This process continues until the entire table is filled. The final answer is in dp[m][n], the bottom-right cell. This method ensures we consider all possible edits efficiently.

Practice

1. What does the Levenshtein distance between two strings measure?

easy

A. The length difference between the two strings

B. The number of matching characters in the same positions

C. The minimum number of single-character edits needed to change one string into the other

D. The number of vowels in both strings combined

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It measures how many single-character edits (insertions, deletions, or substitutions) are needed to convert one string into another.

2. Step 2: Compare with other options

   Options B, C, and D do not describe edit distance but other unrelated string properties.

3. Final Answer:

   The minimum number of single-character edits needed to change one string into the other -> Option C

4. Quick Check:

   Levenshtein distance = minimum edits [OK]

Hint: Think of edits needed to transform one word into another [OK]

Common Mistakes:

• Confusing edit distance with matching characters count
• Thinking it measures length difference only
• Assuming it counts only substitutions

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

easy

A. function levenshtein(s1, s2) { /* code */ }

B. function levenshtein(s1, s2, s3) { /* code */ }

C. function levenshtein() { /* code */ }

D. function levenshtein(s1) { /* code */ }

Solution

1. Step 1: Identify required parameters for Levenshtein function

   The function needs exactly two strings to compare, so it should accept two parameters.

2. Step 2: Check options for correct parameter count

   function levenshtein(s1, s2) { /* code */ } has two parameters (s1, s2), which is correct. Options A, B, and C have incorrect parameter counts.

3. Final Answer:

   function levenshtein(s1, s2) { /* code */ } -> Option A

4. Quick Check:

   Two strings needed as input [OK]

Hint: Levenshtein compares two strings, so function needs two parameters [OK]

Common Mistakes:

• Using wrong number of parameters
• Omitting parameters entirely
• Adding unnecessary extra parameters

3. What is the output of the following JavaScript code snippet?

function min(a, b, c) {
  return Math.min(a, b, c);
}

function levenshtein(s1, s2) {
  const len1 = s1.length;
  const len2 = s2.length;
  const dp = Array(len1 + 1).fill(null).map(() => Array(len2 + 1).fill(0));

  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[len1][len2];
}

console.log(levenshtein('kitten', 'sitting'));

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the Levenshtein distance calculation for 'kitten' and 'sitting'

   Transform 'kitten' to 'sitting' requires 3 substitutions and 1 insertion: k->s, i->i (same), t->t (same), t->t (same), e->i, n->n (same), plus insert 'g'. Total edits = 3.

2. Step 2: Trace the code logic

   The code correctly implements the dynamic programming approach to calculate the minimum edits, returning 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Levenshtein('kitten', 'sitting') = 3 [OK]

Hint: Count edits: substitutions + insertions + deletions [OK]

Common Mistakes:

• Counting only substitutions
• Ignoring insertions or deletions
• Misindexing string characters

4. Identify the bug in the following Levenshtein distance function and select the fix:

function levenshtein(s1, s2) {
  const len1 = s1.length;
  const len2 = s2.length;
  const dp = Array(len1).fill(null).map(() => Array(len2).fill(0));

  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[len1][len2];
}

medium

A. Change loops to run from 0 to len1-1 and len2-1

B. Replace Math.min with Math.max in dp calculation

C. Remove the initialization loops for dp first row and column

D. Change dp array initialization to size (len1+1) x (len2+1)

Solution

1. Step 1: Analyze dp array initialization

   The dp array is initialized with size len1 x len2, but the loops access indices up to len1 and len2, causing out-of-bounds errors.

2. Step 2: Fix dp size to (len1+1) x (len2+1)

   Allocating dp with one extra row and column prevents index errors and allows proper initialization of base cases.

3. Final Answer:

   Change dp array initialization to size (len1+1) x (len2+1) -> Option D

4. Quick Check:

   dp size must match loop bounds [OK]

Hint: dp size must be string length + 1 for indexing [OK]

Common Mistakes:

• Not allocating dp with extra row/column
• Using wrong loop ranges causing errors
• Replacing min with max breaks logic

5. Given two strings s1 = 'intention' and s2 = 'execution', what is the Levenshtein distance between them? Use the concept of minimum edits (insertions, deletions, substitutions) to find the answer.

hard

A. 4

B. 6

C. 5

D. 7

Solution

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

   Transform 'intention' to 'execution' involves substitutions and insertions: i->e, n->x, t->c, e->u, n->t, plus insert 'o'. Total edits count to 6.

2. Step 2: Count minimum edits carefully

   Counting substitutions and insertions needed gives 6 as the minimum number of edits.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Minimum edits between 'intention' and 'execution' = 6 [OK]

Hint: Count each letter change and insertion carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing with string length difference