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:

1. Insert a character
2. Delete a character
3. 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')

Solution 1: DP

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        startOfWord = [[float('inf')] * (n2 + 1) for i in range(n1 + 1)]
        
        # Init ("" & ""), ("" & n1), (n2 & "")
        for i in range(n1 + 1):
            startOfWord[i][n2] = n1 - i
        for j in range(n2 + 1):
            startOfWord[n1][j] = n2 - j
            
        # Compare String start at index i & j
        for i in range(n1 - 1, -1, -1):
            for j in range(n2 - 1, -1, -1):
                if word1[i] == word2[j]:
                    startOfWord[i][j] = startOfWord[i + 1][j + 1]
                else:
                    # 1 Op + (Result for Delete / Insert / Replace)
                    startOfWord[i][j] = 1 + min(startOfWord[i + 1][j], startOfWord[i][j + 1], startOfWord[i + 1][j + 1])
            
        
        return startOfWord[0][0]

Time Complexity: O(N^2)
Space Complexity: O(N^2)

Solution 2:

Time Complexity: O()
Space Complexity: O()

Reference

https://youtu.be/XYi2-LPrwm4

Follow-up: