Understanding Edit Distance in Java

Introduction & Problem Explanation

The Edit Distance (or Levenshtein Distance) problem asks us to find the minimum number of operations required to convert a string word1 to another string word2.

You have three operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

For example, converting word1 = "horse" to word2 = "ros" takes 3 operations:

• horse -> rorse (replace 'h' with 'r')
• rorse -> rose (remove 'r')
• rose -> ros (remove 'e')

This problem is a cornerstone of spell-checkers, DNA sequence analysis, natural language processing, and the popular diff utility. Since recursive exploration results in exponential complexity, we utilize a two-dimensional Dynamic Programming table to solve it.

The Algorithmic Approach

2D Dynamic Programming (O(m * n) Time, O(m * n) Space)

Let m be the length of word1 and n be the length of word2. We create a 2D grid dp of size (m + 1) × (n + 1), where dp[i][j] represents the minimum edit distance between the prefix word1[0..i-1] and word2[0..j-1].

• Base Cases:
  • Converting an empty string to a prefix of length j takes j insertions: dp[0][j] = j.
  • Converting a prefix of length i to an empty string takes i deletions: dp[i][0] = i.
• State Transition: For each character index i in word1 and j in word2:
  • If the characters match (word1.charAt(i - 1) == word2.charAt(j - 1)), no operation is required: dp[i][j] = dp[i - 1][j - 1].
  • If they mismatch, we take the minimum cost of the three operations and add 1:
    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1] (Replace), Math.min(dp[i - 1][j] (Delete), dp[i][j - 1] (Insert)))

The value in the bottom-right cell, dp[m][n], is our final answer.

Step-by-Step Execution Walkthrough

Let's trace the DP matrix setup and transition steps for word1 = "cat" and word2 = "cut":

1. Step 1 (Matrix Setup): Initialize dp array of size 4 × 4:
   • Row 0 (empty word1): [0, 1, 2, 3]
   • Col 0 (empty word2): [0], [1], [2], [3]
2. Step 2 (Cell (1, 1) - 'c' vs 'c'):
   • Characters match! dp[1][1] = dp[0][0] = 0.
3. Step 3 (Cell (1, 2) - 'c' vs 'cu'):
   • Mismatch. dp[1][2] = 1 + min(dp[0][1] (replace), dp[0][2] (insert), dp[1][1] (delete)) = 1 + min(1, 2, 0) = 1.
4. Step 4 (Cell (2, 2) - 'ca' vs 'cu'):
   • Mismatch. Characters are 'a' and 'u'. dp[2][2] = 1 + min(dp[1][1] (replace: 0), dp[1][2] (insert: 1), dp[2][1] (delete: 1)) = 1 + 0 = 1.
5. Step 5 (Cell (3, 3) - 'cat' vs 'cut'):
   • Characters 't' and 't' match! dp[3][3] = dp[2][2] = 1.
6. Step 6 (Result): The bottom-right cell value is 1, which represents replacing 'a' with 'u' in "cat" to get "cut". We return 1.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• dp[i][0] = i; dp[0][j] = j;: Correctly handles the boundary conditions where one of the input strings is empty, defining deletion and insertion baselines.
• word1.charAt(i - 1) == word2.charAt(j - 1): Checks if characters are identical. Matching letters require zero operations, allowing us to inherit the diagonal cost directly.
• Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])): The core choice. Computes the optimal subproblem path out of a replace, delete, or insert operation.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class EditDistance {

    // 2D Dynamic Programming: Time O(M * N), Space O(M * N)
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }

        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Base Case: Convert word1[0..i] to empty word2
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // Base Case: Convert empty word1 to word2[0..j]
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // Fill the 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)) {
                    // Characters match, carry over diagonal value
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // Choose minimum operation: Replace, Delete, or Insert
                    int replace = dp[i - 1][j - 1];
                    int delete = dp[i - 1][j];
                    int insert = dp[i][j - 1];
                    dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        EditDistance solver = new EditDistance();
        String w1 = "horse";
        String w2 = "ros";

        System.out.println("--- Edit Distance Demonstration ---");
        System.out.println("Source Word: " + w1);
        System.out.println("Target Word: " + w2);
        int distance = solver.minDistance(w1, w2);
        System.out.println("Minimum Edit Distance (operations): " + distance); // Expected: 3
    }
}

Conclusion

Edit Distance is a classic example of 2D Dynamic Programming. By mapping prefix relationships onto a grid and reusing matching results, we reduce what would be an exponential recursive search into a clean O(m * n) grid traversal.