72. Edit Distance
happy new year!
please don’t ask DP please don’t ask DP
this one is the more generous DPs where you don’t mandatorily need to think of the states (i.e., didn’t MLE).
1class Solution:
2 @lru_cache(None)
3 def minDistance(self, word1: str, word2: str) -> int:
4 if not word1 or not word2:
5 return max(len(word1), len(word2))
6
7 if word1[0] == word2[0]:
8 return self.minDistance(word1[1:], word2[1:])
9 else:
10 i = self.minDistance(word1, word2[1:]) + 1
11 d = self.minDistance(word1[1:], word2) + 1
12 r = self.minDistance(word1[1:], word2[1:]) + 1
13 return min(i, d, r)
#String #Dynamic-Programming #Python #Revisit