Edit Distance Problem Levenshtein in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the 2D array for dynamic programming.

DSA Java

int[][] dp = new int[[1] + 1][[2] + 1];

Drag options to blanks, or click blank then click option'

Aword1.length()

Bword2.length()

CMath.max(word1.length(), word2.length())

Dword1.length() + word2.length()

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the lengths of word1 and word2.

Forgetting to add 1 to the length.

The dp array has dimensions (word1.length() + 1) by (word2.length() + 1) to account for all prefixes including empty strings.

2fill in blank

medium

Complete the code to fill the first row of the dp array.

DSA Java

for (int j = 0; j <= word2.length(); j++) {
    dp[0][j] = [1];
}

Drag options to blanks, or click blank then click option'

Aword2.length()

Bj

Cword1.length()

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[0][j] to 0 which ignores insertions.

Using word lengths instead of the loop variable j.

The first row represents converting an empty string to the first j characters of word2, so dp[0][j] = j.

3fill in blank

hard

Fix the error in the condition to check if characters are equal.

DSA Java

if (word1.charAt(i - 1) [1] word2.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1];
}

Drag options to blanks, or click blank then click option'

A==

B!=

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' which reverses the logic.

Using relational operators like '>' or '<' which are invalid for char comparison here.

We check if characters are equal using '=='. If equal, no operation is needed, so dp[i][j] = dp[i-1][j-1].

4fill in blank

hard

Fill both blanks to compute the minimum edit distance when characters differ.

DSA Java

dp[i][j] = 1 + Math.min(dp[i - 1][j], [1](dp[i][j - 1], [2]));

Drag options to blanks, or click blank then click option'

AMath.min

BMath.max

Cdp[i - 1][j - 1]

Ddp[i][j]

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.max instead of Math.min.

Using dp[i][j] inside the min function causing incorrect recursion.

We use Math.min to find the smallest cost among deletion, insertion, and substitution (dp[i-1][j-1]).

5fill in blank

hard

Fill all three blanks to complete the nested loops for filling dp array.

DSA Java

for (int i = 1; i <= [1]; i++) {
    for (int j = 1; j <= [2]; j++) {
        if ([3]) {
            dp[i][j] = dp[i - 1][j - 1];
        }
    }
}

Drag options to blanks, or click blank then click option'

Aword1.length()

Bword2.length()

Cword1.charAt(i - 1) == word2.charAt(j - 1)

Dword2.charAt(j - 1)

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop limits causing index errors.

Incorrect character comparison syntax.

The outer loop runs from 1 to word1 length, inner loop from 1 to word2 length, and the condition compares characters at i-1 and j-1.

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