Edit Distance medium

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')

Steps and Explanation

This problem can be solved using dynamic programming. We create a DP table dp where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.

The base cases are:

• dp[i][0] = i for all i (to convert a string of length i to an empty string, we need i deletions).
• dp[0][j] = j for all j (to convert an empty string to a string of length j, we need j insertions).

For i > 0 and j > 0, we have three possibilities:

1. Replace: If word1[i-1] == word2[j-1], no operation is needed, so dp[i][j] = dp[i-1][j-1]. If they are different, we need one replacement, so dp[i][j] = dp[i-1][j-1] + 1.
2. Insert: Insert a character into word1 to match word2[j-1]. This costs 1 operation, so dp[i][j] = dp[i][j-1] + 1.
3. Delete: Delete a character from word1. This costs 1 operation, so dp[i][j] = dp[i-1][j] + 1.

We take the minimum of these three possibilities:

dp[i][j] = min(dp[i-1][j-1] + (word1[i-1] != word2[j-1] ? 1 : 0), dp[i-1][j] + 1, dp[i][j-1] + 1)

Code

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        // Base cases
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        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)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }

        return dp[m][n];
    }
}

Complexity

• Time Complexity: O(mn), where m and n are the lengths of word1 and word2 respectively. This is because we iterate through the DP table of size (m+1) x (n+1).
• Space Complexity: O(mn), due to the DP table. We could optimize this to O(min(m,n)) space by using only two rows of the DP table at a time.