Python DP Solution


  • 0

    dp[i][j] denotes how many operations need to be executed before word1[:i] == word2[:j].

    class Solution(object):
        def minDistance(self, word1, word2):
            dp = [ [0 for i in xrange(len(word2) + 1)] for j in xrange(len(word1) + 1) ]
            dp[0][0] = 0
            for i in xrange(len(word1)):
                dp[i + 1][0] = i + 1
            for i in xrange(len(word2)):
                dp[0][i + 1] = i + 1
            for i in xrange(len(word1)):
                for j in xrange(len(word2)):
                    if word1[i] == word2[j]:
                        dp[i + 1][j + 1] = min(dp[i][j], 1 + dp[i + 1][j], 1 + dp[i][j + 1])
                    else:
                        dp[i + 1][j + 1] = min(1 + dp[i][j], 1 + dp[i + 1][j], 1 + dp[i][j + 1])
            return dp[-1][-1] 
    

Log in to reply
 

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