Python DP solution that beats 57.58%.


  • 0
    M
        def minDistance(self, word1, word2):
            m, n = len(word1), len(word2)
            r = [[0 for _ in xrange(n+1)] for _ in xrange(m+1)]
            for i in xrange(m, -1, -1):
                for j in xrange(n, -1, -1):
                    if i == m or j == n:
                        r[i][j] = max(m-i, n-j)
                    elif word1[i] == word2[j]:
                        r[i][j] = r[i+1][j+1]
                    else:
                        r[i][j] = 1 + min(r[i+1][j], r[i][j+1], r[i+1][j+1])
            return r[0][0]
    

Log in to reply
 

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