Edit Distance Problem Levenshtein in DSA Java - 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

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

Execution Sample

DSA Java

String s1 = "kitten";
String s2 = "sitting";
int[][] dp = new int[s1.length()+1][s2.length()+1];
// Fill dp table
// dp[m][n] is the answer

This code sets up the DP table to find the minimum edits to convert "kitten" to "sitting".

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table Snapshot
1	Initialize dp[0][j]	(0,0 to 0,7)	N/A	dp[0][j] = j	[0,1,2,3,4,5,6,7] [ , , , , , , , ] [ , , , , , , , ] [ , , , , , , , ] [ , , , , , , , ] [ , , , , , , , ] [ , , , , , , , ]
2	Initialize dp[i][0]	(1,0 to 6,0)	N/A	dp[i][0] = i	[0,1,2,3,4,5,6,7] [1, , , , , , , ] [2, , , , , , , ] [3, , , , , , , ] [4, , , , , , , ] [5, , , , , , , ] [6, , , , , , , ]
3	Compare 'k' and 's'	(1,1)	'k' vs 's'	1 + min(1,1,0) = 1	[0,1,2,3,4,5,6,7] [1,1, , , , , , ] [2, , , , , , , ] [3, , , , , , , ] [4, , , , , , , ] [5, , , , , , , ] [6, , , , , , , ]
4	Compare 'k' and 'i'	(1,2)	'k' vs 'i'	1 + min(1,1,1) = 2	[0,1,2,3,4,5,6,7] [1,1,2, , , , , ] [2, , , , , , , ] [3, , , , , , , ] [4, , , , , , , ] [5, , , , , , , ] [6, , , , , , , ]
5	Compare 'i' and 'i'	(2,2)	'i' vs 'i'	dp[1][1] = 1	[0,1,2,3,4,5,6,7] [1,1,2, , , , , ] [2,2,1, , , , , ] [3, , , , , , , ] [4, , , , , , , ] [5, , , , , , , ] [6, , , , , , , ]
6	Fill rest of dp table step-by-step	(i,j)	Compare s1[i-1] and s2[j-1]	Calculate dp[i][j]	Table fills with minimum edits for each prefix pair
7	Final answer	(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,3,3]

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 7	Final
dp[0][j]	empty	[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]	empty	empty	[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[i][j]	empty	empty	partial	partial	mostly filled	fully filled
i	0	1	2	6	6	6
j	0	1	2	7	7	7

Key Moments - 3 Insights

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

Because converting an empty string to a string of length j requires j insertions, and converting a string of length i to an empty string requires i deletions. This is shown in execution_table rows 1 and 2.

Why do we add 1 plus the minimum of three neighboring cells when characters differ?

Because one edit operation (insert, delete, or replace) is needed plus the minimum edits from previous states. This is shown in execution_table row 3 where dp[i][j] = 1 + min(insert, delete, replace).

Why does dp[i][j] equal dp[i-1][j-1] when characters are the same?

Because no edit is needed if characters match, so the cost stays the same as the previous prefix comparison. This is shown in execution_table row 5.

Visual Quiz - 3 Questions

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

A 0

B 1

C 2

D 3

💡 Hint

Check execution_table row 3 under 'DP Cell Value' for dp[1][1]

At which step does the dp table first show a cell value equal to the previous diagonal cell because characters matched?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at execution_table row 5 where 'i' and 'i' are compared and dp[i][j] equals dp[i-1][j-1]

If the first string was empty, how would the dp table initialization change?

A First row would be zeros

B First column would be zeros

C First row would be increasing numbers, first column zeros

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

💡 Hint

Refer to variable_tracker for dp[0][j] initialization and key_moments about empty string conversions

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 dp[0][j] = j and dp[i][0] = i.
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].

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 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 conversions from or to empty strings. Then, for each cell, we compare characters: if they match, no new edit is needed, so we copy the diagonal value. If they differ, we add one edit to the minimum of insert, delete, or replace operations from neighboring cells. The final answer is found at dp[m][n], where m and n are the lengths of the two strings. This step-by-step filling of the table ensures we consider all possible edit sequences and find the minimum cost.

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 characters that are the same in both strings

C. The length difference between two strings

D. The maximum number of matching characters in order

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes are needed to turn one string into another using insert, delete, or substitute operations.

2. Step 2: Compare options with definition

   Only The minimum number of insertions, deletions, or substitutions to convert one string into another correctly describes the minimum number of these operations needed.

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 [OK]

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

Common Mistakes:

• Confusing edit distance with common substring length
• Thinking it measures only character matches
• Assuming it counts only insertions or deletions

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

easy

A. public boolean levenshteinDistance(String s1, String s2)

B. public void levenshteinDistance(String s1, String s2)

C. public String levenshteinDistance(String s1, String s2)

D. public int levenshteinDistance(String s1, String s2)

Solution

1. Step 1: Identify the return type for Levenshtein distance

   The Levenshtein distance is a number representing the count of edits, so the return type should be int.

2. Step 2: Check method signature correctness

   public int levenshteinDistance(String s1, String s2) returns int and takes two String parameters, which is correct. Other options return void, String, or boolean, which are incorrect for this purpose.

3. Final Answer:

   public int levenshteinDistance(String s1, String s2) -> Option D

4. Quick Check:

   Return type int for distance [OK]

Hint: Distance is a number, so return int [OK]

Common Mistakes:

• Using void return type and not returning a value
• Returning String instead of int
• Returning boolean which is not suitable

3. What is the Levenshtein distance between the strings "kitten" and "sitting"?

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Compare strings and count edits

   Transform "kitten" to "sitting": substitute 'k'->'s', substitute 'e'->'i', insert 'g' at end. Total edits = 3.

2. Step 2: Confirm minimal edits

   No fewer than 3 edits can convert "kitten" to "sitting".

3. Final Answer:

   3 -> Option B

4. Quick Check:

   kitten -> sitting needs 3 edits [OK]

Hint: Count substitutions, insertions, deletions carefully [OK]

Common Mistakes:

• Counting only substitutions and missing insertions
• Miscounting edits by skipping characters
• Assuming length difference equals distance

4. Given the following Java code snippet to compute Levenshtein distance, what is the error?

public int levenshteinDistance(String s1, String s2) {
  int[][] dp = new int[s1.length()][s2.length()];
  for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
      if (i == 0) dp[i][j] = j;
      else if (j == 0) dp[i][j] = i;
      else if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
    }
  }
  return dp[s1.length()][s2.length()];
}

medium

A. The return statement should return dp[s1.length()-1][s2.length()-1]

B. The loops should start from 1 instead of 0

C. Array dp is declared with wrong size causing IndexOutOfBoundsException

D. The character comparison uses wrong indices

Solution

1. Step 1: Check dp array size

   dp is declared as new int[s1.length()][s2.length()] but loops run up to s1.length() and s2.length() inclusive, causing index out of bounds.

2. Step 2: Identify correct dp size

   dp should be new int[s1.length()+1][s2.length()+1] to accommodate indices up to s1.length() and s2.length().

3. Final Answer:

   Array dp is declared with wrong size causing IndexOutOfBoundsException -> Option C

4. Quick Check:

   dp size must be length+1 [OK]

Hint: dp array size must be lengths + 1 [OK]

Common Mistakes:

• Declaring dp with exact string lengths only
• Returning dp at wrong indices
• Starting loops incorrectly causing errors

5. What is the Levenshtein distance between the strings "intention" and "execution"?

hard

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Align the strings and identify differences

   Both strings have length 9. The minimal edit sequence includes substitutions and insertions/deletions. The Levenshtein distance is 6, as confirmed by standard DP computation.

2. Step 2: Confirm no better alignment

   Insertions/deletions and substitutions combined yield a minimum of 6 edits.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   intention -> execution = 6 [OK]

Hint: Align strings and compute minimum operations via mismatches or DP trace [OK]

Common Mistakes:

• Counting 6 by proposing unnecessary insert/delete
• Underestimating by ignoring all mismatches (e.g., 4)
• Overestimating due to poor alignment