Share my python solution, use memo.


  • 0
    L

    use the memo method,.

    class Solution:
    # @return an integer
    def minDistance(self, word1, word2):
    
        def minDisCore(word1,word2,hash):
            if(word1==word2):return 0;
            if(len(word1)==0):return len(word2);
            if(len(word2)==0):return len(word1);
    
            key=word1+"##"+word2;
            if(key in hash):
                return hash[key];
            else:
                res=0;
                if(word1[0]==word2[0]):
                    res= minDisCore(word1[1:],word2[1:],hash);
                else:
                    res= min(minDisCore(word1[1:],word2,hash)+1,  # insert mode
                             minDisCore(word1,word2[1:],hash)+1,  # insert mode
                             minDisCore(word1[1:],word2[1:],hash)+1); # update mode
                hash[key]=res;
            return hash[key];
    
        return minDisCore(word1,word2,{});

Log in to reply
 

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