Python recursive solution with memorization


  • 0
    W

    Just to give a different view from DP. Quite efficient for this problem (139 ms beating 98%).

    class Solution(object):
        def minDistance(self, w1, w2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            m,n,d = len(w1),len(w2),{}
            def mds(w1, w2, i, j):
                if i*j==0: return i+j
                if (i,j) in d: return d[(i,j)]
                val = 0
                if w1[i-1]==w2[j-1]:
                    val = mds(w1, w2, i-1, j-1)
                else:
                    val = 1+min(mds(w1,w2,i,j-1),mds(w1,w2,i-1,j-1),mds(w1,w2,i-1,j))
                d[(i,j)]=val
                return val
            return mds(w1,w2,m,n)
    

Log in to reply
 

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