LeetCode 72. Edit Distance

Question

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')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Source: https://leetcode.com/problems/edit-distance/

Solution

To make word1[:i] equal to word2[:j], there are 4 possible actions on their last characters: no operation (only when their last characters are identical), insert, delete, and replace. In each step, we only consider the last characters in the two strings.

Note that i,j in the following illustration and those in the code have different meanings. Dependencies in the transition equation determine the order of the loops.

// Time Complexity O(mn)
// Space Complexity O(mn)
public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return -1;
    }
    int len1 = word1.length();
    int len2 = word2.length();
    if (len1 == 0) { // word1 is ""
        return len2;
    }
    if (len2 == 0) { // word2 is ""
        return len1;
    }

    // dp[i][j] is the min number of operations to make word1[0, i) equals word2[0, j)
    int[][] dp = new int[len1 + 1][len2 + 1];
    // init
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j; // always insert
    }
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i; // always delete
    }
    // transition
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            int noOp = dp[i - 1][j - 1]; // can only be used if word1[i - 1] == word2[j - 1]
            int replaceOp = 1 + dp[i - 1][j - 1];
            int deleteOp = 1 + dp[i - 1][j];
            int insertOp = 1 + dp[i][j - 1];
            // consider all possible choices
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) { // no need replace
                dp[i][j] = Math.min(noOp, Math.min(deleteOp, insertOp));
            } else {
                dp[i][j] = Math.min(replaceOp, Math.min(deleteOp, insertOp));
            }
        }
    }
    return dp[len1][len2];
}