Edit Distance

• Define a recursive function solve(i, j) that takes two indices representing the end of the prefixes of word1 and word2.
• Base Case 1: If i is less than 0 (meaning word1's prefix is empty), we need to insert all remaining characters of word2. The cost is j + 1.
• Base Case 2: If j is less than 0 (meaning word2's prefix is empty), we need to delete all remaining characters of word1. The cost is i + 1.
• Recursive Step (Characters Match): If word1.charAt(i) is the same as word2.charAt(j), no operation is needed for these characters. We simply recurse on the smaller prefixes: solve(i - 1, j - 1).
• Recursive Step (Characters Differ): If the characters are different, we must perform an operation. We explore all three possibilities and take the one with the minimum cost:
  • Insert: 1 + solve(i, j - 1)
  • Delete: 1 + solve(i - 1, j)
  • Replace: 1 + solve(i - 1, j - 1)
• The initial call to the function is solve(word1.length() - 1, word2.length() - 1).

The core idea is to make a decision at each step based on the last characters of the current prefixes of word1 and word2.

If the characters word1[i] and word2[j] match, they contribute nothing to the edit distance. The problem reduces to finding the edit distance for the strings without these last characters, which is a recursive call solve(i-1, j-1).

If the characters do not match, we have three choices:

1. Insert: We can insert word2[j] into word1 to match it. The problem then becomes converting word1[0...i] to word2[0...j-1]. The cost is 1 + solve(i, j-1).
2. Delete: We can delete word1[i]. The problem becomes converting word1[0...i-1] to word2[0...j]. The cost is 1 + solve(i-1, j).
3. Replace: We can replace word1[i] with word2[j]. The problem becomes converting word1[0...i-1] to word2[0...j-1]. The cost is 1 + solve(i-1, j-1).

We take the minimum of these three options. The base cases handle situations where one of the strings becomes empty.

1class Solution {2    public int minDistance(String word1, String word2) {3        return solve(word1, word2, word1.length() - 1, word2.length() - 1);4    }5 6    private int solve(String word1, String word2, int i, int j) {7        // Base case: If word1 is empty, we need to insert all characters of word2.8        if (i < 0) {9            return j + 1;10        }11        // Base case: If word2 is empty, we need to delete all characters of word1.12        if (j < 0) {13            return i + 1;14        }15 16        // If the last characters are the same, no operation is needed.17        if (word1.charAt(i) == word2.charAt(j)) {18            return solve(word1, word2, i - 1, j - 1);19        } else {20            // If last characters are different, consider all three operations.21            int insertOp = solve(word1, word2, i, j - 1);22            int deleteOp = solve(word1, word2, i - 1, j);23            int replaceOp = solve(word1, word2, i - 1, j - 1);24            25            return 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));26        }27    }28}

• Create a 2D array memo of size (m+1) x (n+1) to store the results of subproblems, initialized with a value like -1.
• Define a recursive function solve(i, j) that takes the current lengths of the prefixes.
• Base Cases: If i is 0, return j. If j is 0, return i.
• Memoization Check: Before computing, check if memo[i][j] is not -1. If it's not, return the stored value immediately.
• Recursive Step (Characters Match): If word1.charAt(i-1) == word2.charAt(j-1), the result is solve(i-1, j-1).
• Recursive Step (Characters Differ): Otherwise, the result is 1 + min(solve(i, j-1), solve(i-1, j), solve(i-1, j-1)).
• Store Result: Before returning the computed result, store it in memo[i][j].
• The initial call is solve(m, n).

We observe that the brute-force recursive solution repeatedly solves the same subproblems (e.g., solve(i, j) is called from multiple different paths). Memoization addresses this by caching the results.

We use a 2D array, memo, where memo[i][j] will store the minimum edit distance between the first i characters of word1 and the first j characters of word2. The array is initialized with a sentinel value (like -1) to indicate that a state has not been computed.

In our recursive function, the first step is to check the memo table. If a result for the current state (i, j) exists, we return it instantly. Otherwise, we perform the same logic as the brute-force approach to compute the result. Crucially, before returning, we save this newly computed result in memo[i][j] for future use.

This ensures that each of the m * n subproblems is calculated only once.

1class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length();4        int n = word2.length();5        int[][] memo = new int[m + 1][n + 1];6        for (int[] row : memo) {7            java.util.Arrays.fill(row, -1);8        }9        return solve(word1, word2, m, n, memo);10    }11 12    private int solve(String word1, String word2, int i, int j, int[][] memo) {13        if (i == 0) {14            return j;15        }16        if (j == 0) {17            return i;18        }19        if (memo[i][j] != -1) {20            return memo[i][j];21        }22 23        int result;24        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {25            result = solve(word1, word2, i - 1, j - 1, memo);26        } else {27            int insertOp = solve(word1, word2, i, j - 1, memo);28            int deleteOp = solve(word1, word2, i - 1, j, memo);29            int replaceOp = solve(word1, word2, i - 1, j - 1, memo);30            result = 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));31        }32        33        memo[i][j] = result;34        return result;35    }36}

• Let m = word1.length() and n = word2.length().
• Create a 2D array dp of size (m+1) x (n+1).
• Initialize Base Cases:
  • Fill the first row: dp[0][j] = j for j from 0 to n. (Cost of insertions)
  • Fill the first column: dp[i][0] = i for i from 0 to m. (Cost of deletions)
• Fill the Table:
  • Iterate with i from 1 to m.
  • Iterate with j from 1 to n.
  • If word1.charAt(i-1) == word2.charAt(j-1):
    • dp[i][j] = dp[i-1][j-1] (No operation cost)
  • Else:
    • dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (Cost of delete, insert, or replace)
• The final answer is the value in the bottom-right cell, dp[m][n].

The tabulation approach constructs the solution iteratively. We create a dp table of size (m+1) x (n+1).

First, we establish the base cases. dp[0][j] represents converting an empty string to a prefix of word2 of length j, which requires j insertions. So, dp[0][j] = j. Similarly, dp[i][0] represents converting a prefix of word1 of length i to an empty string, requiring i deletions. So, dp[i][0] = i.

Then, we fill the rest of the table row by row, column by column. To compute dp[i][j], we look at the characters word1[i-1] and word2[j-1].

• If they match, the cost is the same as the subproblem for prefixes i-1 and j-1, so dp[i][j] = dp[i-1][j-1].
• If they differ, we need one operation. The total cost will be 1 plus the minimum of the costs of the three preceding states:
  • dp[i-1][j]: Cost if we delete word1[i-1].
  • dp[i][j-1]: Cost if we insert word2[j-1].
  • dp[i-1][j-1]: Cost if we replace word1[i-1] with word2[j-1].

The final answer is dp[m][n], which represents the edit distance for the full strings.

1class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length();4        int n = word2.length();5        6        int[][] dp = new int[m + 1][n + 1];7        8        // Initialize base cases9        for (int i = 0; i <= m; i++) {10            dp[i][0] = i; // Cost of deleting i chars from word1 to get an empty string11        }12        for (int j = 0; j <= n; j++) {13            dp[0][j] = j; // Cost of inserting j chars to an empty string to get word214        }15        16        // Fill the DP table17        for (int i = 1; i <= m; i++) {18            for (int j = 1; j <= n; j++) {19                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {20                    dp[i][j] = dp[i - 1][j - 1];21                } else {22                    int deleteOp = dp[i - 1][j];23                    int insertOp = dp[i][j - 1];24                    int replaceOp = dp[i - 1][j - 1];25                    dp[i][j] = 1 + Math.min(deleteOp, Math.min(insertOp, replaceOp));26                }27            }28        }29        30        return dp[m][n];31    }32}

• To minimize space, ensure word2 is the shorter string (if not, swap the strings). Let m be the length of the longer string and n be the length of the shorter one.
• Create a 1D array dp of size n+1.
• Initialize dp as the first row of the conceptual 2D table: dp[j] = j for j from 0 to n.
• Iterate i from 1 to m (for each character of the longer string):
  • Store the top-left diagonal value needed for the first column calculation: prev_val = dp[0].
  • Update the first element of the current row: dp[0] = i.
  • Iterate j from 1 to n:
    • Store the value from the previous row, dp[j], in a temp variable before it's overwritten. This is the dp[i-1][j] value.
    • If word1.charAt(i-1) == word2.charAt(j-1), then dp[j] = prev_val.
    • Else, dp[j] = 1 + min(dp[j-1], temp, prev_val).
    • Update prev_val = temp to be used in the next j iteration as the new diagonal value.
• Return dp[n].

Instead of a full 2D table, we can use a single 1D array, say dp, of size n+1 (where n is the length of the shorter string to save space). This dp array will be used to compute the current row's values based on the previous row's values which it already holds.

When we compute dp[j] (representing the cell (i, j) in the 2D version), we need:

1. dp[i][j-1] (Insert): This is dp[j-1] in our 1D array, which has just been computed for the current row i.
2. dp[i-1][j] (Delete): This is the value that dp[j] held before we started computing the current row i. We save this in a temp variable.
3. dp[i-1][j-1] (Replace/Match): This was the value of dp[j-1] from the previous row. We use another variable, prev_val, to track this diagonal value as we iterate across the row.

By carefully managing prev_val and a temp variable inside the inner loop, we can simulate the 2D table's calculations using only one array.

1class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length();4        int n = word2.length();5 6        // Ensure word2 is the shorter string to optimize space7        if (m < n) {8            // Swap strings and lengths to call recursively9            return minDistance(word2, word1);10        }11 12        // Now m >= n. We use an array of size n+1.13        int[] dp = new int[n + 1];14 15        // Initialize the dp array as if word1 is empty16        for (int j = 0; j <= n; j++) {17            dp[j] = j;18        }19 20        // Iterate through word121        for (int i = 1; i <= m; i++) {22            int prev_val = dp[0]; // This is dp[i-1][j-1] for j=123            dp[0] = i; // Base case for the current row i24 25            // Iterate through word226            for (int j = 1; j <= n; j++) {27                int temp = dp[j]; // This is dp[i-1][j]28                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {29                    dp[j] = prev_val;30                } else {31                    // dp[j-1] is dp[i][j-1] (insert)32                    // temp is dp[i-1][j] (delete)33                    // prev_val is dp[i-1][j-1] (replace)34                    dp[j] = 1 + Math.min(dp[j - 1], Math.min(temp, prev_val));35                }36                prev_val = temp;37            }38        }39 40        return dp[n];41    }42}