0072. Edit Distance

Hard | String + DP | 88 ms (98.31%), 16.6 MB (84.05%)

❓ Problem Statement

Source: LeetCode - Edit Distance GitHub: Solution / Performance

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

✍🏻 Constraints & Example

Constraints:

• 0 <= word1.length, word2.length <= 500

• word1 and word2 consist of lowercase English letters.

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

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

💡 Ideas

We simulate and figure out the cost of the following four operations:

• Delete = 1 modification (Delete char in word1) Move to the next char in word1 to compare. So we take table[i-1][j]

• Insert = 1 modification (Insert char to word1) Move to the next char in word2 to compare. So we take table[i][j-1]

• Replace = 1 modification (Replace the char in word1) Move to the next char in both word1 and word2 to compare. So we take table[i-1][j-1]

• Skip = 0 modification (Two chars are the same) Move to the next char in both word1 and word2 to compare. So we take table[i-1][j-1]

We create a 2D array and initialize values on table[i][0] and table[0][j]

Then iterate through each char by the nested for loops to find the minimum operations. i in range(1, len(word1) + 1) j in range(1, len(word2) + 1)

🤖 Python3

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # (base case)
        if not word1 and not word2: return 0
        if not word1 or not word2: return len(word1) + len(word2)

        # ==================================================
        #  String + Dynamic Programming                    =
        # ==================================================
        # time  : O(mn)
        # space : O(mn)
        
        table = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for i in range(len(word1) + 1): table[i][0] = i
        for j in range(len(word2) + 1): table[0][j] = j
        
        '''
        [[0, 1, 2, 3], 
         [1, 0, 0, 0], 
         [2, 0, 0, 0], 
         [3, 0, 0, 0], 
         [4, 0, 0, 0], 
         [5, 0, 0, 0]]
         '''
        
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i - 1] == word2[j - 1]: table[i][j] = table[i-1][j-1]
                else:
                    table[i][j] = 1 + min(table[i-1][j], table[i][j-1], table[i-1][j-1])
        
        return table[-1][-1]

🤖 Java

class Solution {
    /**  
     * @time  : O(mn)
     * @space : O(mn)
     */
     
    String word1, word2;
    int n1, n2;
    int[][] table;
    
    public int minDistance(String word1, String word2) {
        /* base case */
        if(word1 == null && word2 == null) return 0;
        if(word1 == null || word2 == null) return word1.length() + word2.length();
        
        this.word1 = word1;
        this.word2 = word2;
        this.n1 = word1.length();
        this.n2 = word2.length();
            
        this.table = new int[word1.length()][word2.length()];
        for(int i=0 ; i<word1.length() ; i++) {
            Arrays.fill(this.table[i], -1);
        }
        
        return dp(0, 0);
    }
    
    public int dp(int index1, int index2) {
        if(index1 == this.n1) return this.n2 - index2;
        if(index2 == this.n2) return this.n1 - index1;
        
        if(this.table[index1][index2] != -1) return this.table[index1][index2];
        
        if(this.word1.charAt(index1) == this.word2.charAt(index2)) {
            this.table[index1][index2] = dp(index1 + 1, index2 + 1);
            
        } else {
            int insert  = 1 + dp(index1,     index2 + 1);
            int delete  = 1 + dp(index1 + 1, index2);
            int replace = 1 + dp(index1 + 1, index2 + 1);
            
            this.table[index1][index2] = Math.min(Math.min(insert, delete), replace);
        }
        
        return this.table[index1][index2];
    }
}