A simple Python DP solution

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

Log in to reply

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