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

💡 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