Edit Distance Problem Levenshtein in DSA Java

Mental Model

Find the smallest number of changes needed to turn one word into another by inserting, deleting, or replacing letters.

Analogy: Imagine fixing a typo in a word by changing letters, adding missing ones, or removing extras, like editing a sentence to make it correct.

word1: c a t
word2: c a r

We compare letters one by one and count changes needed:

c a t
| | |
c a r

Positions: 0 1 2

Dry Run Walkthrough

Input: word1 = "cat", word2 = "car"

Goal: Calculate the minimum edits to change "cat" into "car"

Step 1: Initialize a 2D table with sizes (4 x 4) for lengths of words plus one

Table rows: ['', 'c', 'a', 't']
Table cols: ['', 'c', 'a', 'r']
Initial table:
  0 1 2 3
0 0 1 2 3
1 1
2 2
3 3

Why: We prepare to store minimum edits for all prefixes of both words

Step 2: Fill first row and column with incremental values representing edits from empty string

  0 1 2 3
0 0 1 2 3
1 1
2 2
3 3

Why: Changing empty string to prefixes requires insertions or deletions equal to prefix length

Step 3: Compare letters 'c' and 'c' (positions 1,1), they match so cost is 0

  0 1 2 3
0 0 1 2 3
1 1 0
2 2
3 3

Why: No edit needed when letters are the same

Step 4: Compare 'a' and 'a' (positions 2,2), they match so cost is 0

  0 1 2 3
0 0 1 2 3
1 1 0 1
2 2 1 0
3 3

Why: No edit needed for matching letters

Step 5: Compare 't' and 'r' (positions 3,3), letters differ so cost is 1

  0 1 2 3
0 0 1 2 3
1 1 0 1 2
2 2 1 0 1
3 3 2 1 1

Why: One replacement needed to change 't' to 'r'

Result:

Minimum edits = 1
Final table:
  0 1 2 3
0 0 1 2 3
1 1 0 1 2
2 2 1 0 1
3 3 2 1 1

Annotated Code

DSA Java

public class EditDistance {

    public static int levenshteinDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Initialize first row and column
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // delete all characters from word1
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // insert all characters to word1
        }

        // Fill dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // no edit needed
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i - 1][j - 1], // replace
                        Math.min(dp[i - 1][j], // delete
                                 dp[i][j - 1]) // insert
                    );
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String word1 = "cat";
        String word2 = "car";
        int distance = levenshteinDistance(word1, word2);
        System.out.println("Minimum edits to convert '" + word1 + "' to '" + word2 + "': " + distance);
    }
}

for (int i = 0; i <= m; i++) { dp[i][0] = i; // delete all characters from word1 }

Initialize first column with deletion costs from word1 to empty string

for (int j = 0; j <= n; j++) { dp[0][j] = j; // insert all characters to word1 }

Initialize first row with insertion costs from empty string to word2

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

If letters match, carry over previous cost without adding edits

else { dp[i][j] = 1 + Math.min( dp[i - 1][j - 1], // replace Math.min(dp[i - 1][j], // delete dp[i][j - 1]) // insert ); }

If letters differ, choose minimum cost among replace, delete, or insert plus one edit

Output

Minimum edits to convert 'cat' to 'car': 1

Complexity Analysis

Time: O(m*n) because we fill a table of size m by n once

Space: O(m*n) because we store edit distances for all prefix pairs

vs Alternative: Naive recursive approach has exponential time due to repeated calculations; DP reduces it to polynomial time by storing results

Edge Cases

One or both strings are empty

Distance equals length of the other string (all insertions or deletions)

DSA Java

for (int i = 0; i <= m; i++) {
    dp[i][0] = i; // delete all characters from word1
}

Both strings are identical

Distance is zero because no edits are needed

DSA Java

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

Strings differ by one character

Distance is one due to one replacement, insertion, or deletion

DSA Java

else {
    dp[i][j] = 1 + Math.min(
        dp[i - 1][j - 1], // replace
        Math.min(dp[i - 1][j], // delete
                 dp[i][j - 1]) // insert
    );
}

When to Use This Pattern

When asked to find the minimum number of changes to convert one string into another, use the Levenshtein distance dynamic programming pattern because it efficiently counts edits.

Common Mistakes

Mistake: Not initializing the first row and column of the DP table
Fix: Explicitly fill first row and column to represent edits from empty strings

Mistake: Comparing characters without adjusting for zero-based indexing
Fix: Use i-1 and j-1 when accessing characters to match DP indices

Mistake: Using max instead of min when choosing edit operations
Fix: Always pick the minimum cost among replace, insert, and delete plus one

Summary

Calculates the smallest number of insertions, deletions, or replacements to change one word into another.

Use when you need to measure how different two strings are or find the minimal edits to convert between them.

The key insight is building a table that stores solutions for smaller parts (prefixes) to solve the whole problem efficiently.

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