Dynamic Programming Solution in Python

  • 1

    Why everyone is using Java?

    class Solution:
        # @return an integer
        def minDistance(self, word1, word2):
            cache = {(0,0):0}
            distance = 0
            for i in range(len(word1)+1):
                cache[(i,0)] = i
            for j in range(len(word2)+1):
                cache[(0,j)] = j
            for i in range(1, len(word1)+1):
                for j in range(1, len(word2)+1):
                    if word1[i-1] == word2[j-1]:
                        cache[(i,j)] = cache[(i-1,j-1)]
                        cache[(i,j)] = min(cache[(i-1,j)], cache[(i,j-1)], cache[(i-1,j-1)])+1
            return cache[(len(word1),len(word2))]

Log in to reply

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