Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character Delete a character 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') Example 2:
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')
My code:
import numpy as np
class Solution:
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if len(word1)==0:
return len(word2)
if len(word2)==0:
return len(word1)
self.matrix=np.zeros([len(word1),len(word2)])-1
count=self.common(word1,word2,len(word1)-1,len(word2)-1)
#print(self.matrix)
#print(len(word2))
#all_length=max([len(word1),len(word2)])
return int(count)
def common(self,word1,word2,i,j):
if i<0:
return j+1
if j<0:
return i+1
if self.matrix[i,j]!=-1:
return self.matrix[i,j]
if word1[i]==word2[j]:
count0=self.common(word1,word2,i-1,j-1)
self.matrix[i,j]=count0
return count0
else:
count0=self.common(word1,word2,i-1,j-1)+1
count1=1+self.common(word1,word2,i-1,j)
count2=1+self.common(word1,word2,i,j-1)
self.matrix[i,j]=min([count0,count1,count2])
return self.matrix[i,j]