Python dp solution


  • 0
    P
        def  minDistance(self, strWord1, strWord2):
            res = [[0]*(len(strWord2)+1) for _ in range(len(strWord1)+1)]
    
            # handle extreme conditions first
            res[len(strWord1)][len(strWord2)] = 0
    
            for j in range(len(strWord2)+1):
                res[len(strWord1)][j] = len(strWord2)-j
    
            for i in range(len(strWord1)+1):
                res[i][len(strWord2)] = len(strWord1)-i
    
            for i in range(len(strWord1), -1, -1):
                for j in range(len(strWord2), -1, -1):
                    if i == len(strWord1) or j == len(strWord2):
                        continue
                    d = 0    
                    if strWord1[i]==strWord2[j]:
                        d = res[i+1][j+1]
                    else:
                        d = min(res[i][j+1], res[i+1][j], res[i+1][j+1]) + 1 
                    res[i][j] = d    
    
            return res[0][0]
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.