Edit Distance Problem Levenshtein in DSA Java - Build from Scratch

Edit Distance Problem Levenshtein

📖 Scenario: Imagine you are building a spell checker that suggests corrections for misspelled words. To do this, you need to find how different two words are by counting the minimum number of edits needed to change one word into another. These edits can be inserting, deleting, or replacing a character.

🎯 Goal: You will write a Java program that calculates the Levenshtein edit distance between two words. This distance tells you the minimum number of single-character edits required to change one word into the other.

📋 What You'll Learn

Create two string variables with exact values

Create an integer variable to store the length of the first string

Create an integer variable to store the length of the second string

Implement the Levenshtein distance calculation using a 2D array

Print the final edit distance value

💡 Why This Matters

🌍 Real World

Spell checkers, auto-correct features, DNA sequence analysis, and natural language processing use edit distance to find how similar two strings are.

💼 Career

Understanding dynamic programming and string algorithms is essential for software engineers working on text processing, search engines, and bioinformatics.

1

Create the input strings

Create two string variables called word1 and word2 with the exact values "kitten" and "sitting" respectively.

DSA Java

// Create string variables word1 and word2 with values "kitten" and "sitting"
// Your code here

Hint

Use String word1 = "kitten"; and String word2 = "sitting";

2

Create length variables for both strings

Create two integer variables called len1 and len2 that store the lengths of word1 and word2 respectively.

DSA Java

public class EditDistance {
    public static void main(String[] args) {
        String word1 = "kitten";
        String word2 = "sitting";
        // Create integer variables len1 and len2 for lengths of word1 and word2
        // Your code here
    }
}

Hint

Use int len1 = word1.length(); and int len2 = word2.length();

3

Implement the Levenshtein distance calculation

Create a 2D integer array called dp with size (len1 + 1) x (len2 + 1). Use nested for loops with variables i and j to fill dp according to the Levenshtein distance rules: initialize first row and column, then compute minimum edits for each position. Use word1.charAt(i - 1) and word2.charAt(j - 1) to compare characters. Store the final result in an integer variable called distance from dp[len1][len2].

DSA Java

public class EditDistance {
    public static void main(String[] args) {
        String word1 = "kitten";
        String word2 = "sitting";
        int len1 = word1.length();
        int len2 = word2.length();
        // Create dp array and fill it with Levenshtein distance logic
        // Your code here
    }
}

Hint

Initialize the first row and column with index values. Then use nested loops to fill the rest of the dp array. Use Math.min to find the minimum of delete, insert, and replace operations.

4

Print the final edit distance

Print the integer variable distance using System.out.println to display the Levenshtein edit distance between word1 and word2.

DSA Java

public class EditDistance {
    public static void main(String[] args) {
        String word1 = "kitten";
        String word2 = "sitting";
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        int distance = dp[len1][len2];
        // Print the distance
        // Your code here
    }
}

Hint

Use System.out.println(distance); to print the final edit distance.

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