動機

insert是最難想的部分

Problem

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 = rosOutput: 3Explanation: horse -> rorse (replace 'h' with 'r')rorse -> rose (remove 'r')rose -> ros (remove 'e')

Example 2:

Input: word1 = intention, word2 = executionOutput: 5Explanation: 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.

Sol

用兩個index表示比到哪裡，如果一樣就一起後退 不一樣就要經歷insert, replace, 或 delete

replace很好理解，就是換成一樣的，這樣兩個就一起後退

delete也不難想像，就是刪第一個string，所以只退第一個

但insert對我就不好理解，最後想到的理解方式是

因為第一個string目前的index沒有動，所以不變，但是多了match第二個string的字，所以第二個要後退

像"123"在index是2的地方insert，就會變成"1234"，然而index還是在2，但第二個string一定會被match，所以第二個要後退

class Solution:
    def __init__(self):
        self.dp = {}
    def f(self,s1,s2,i,j):
        if (i,j) not in self.dp:
            if i < 0 and j < 0:
                return 0
            elif i < 0:
                self.dp[(i,j)] = self.f(s1,s2,i,j-1) + 1
            elif j < 0:
                self.dp[(i,j)] = self.f(s1,s2,i-1,j) + 1
            elif s1[i] == s2[j]:
                self.dp[(i,j)] = self.f(s1,s2,i-1,j-1)
            else:
                self.dp[(i,j)] = min(self.f(s1,s2,i-1,j-1),self.f(s1,s2,i,j-1),self.f(s1,s2,i-1,j))+1
        
        return self.dp[(i,j)]
    def minDistance(self, word1: str, word2: str) -> int:
        self.dp = {}
        return self.f(word1,word2,len(word1)-1,len(word2)-1)