Share my Python DP solution

  • 0
    class Solution(object):
        def minDistance(self, word1, word2):
            m,n = len(word1), len(word2)
            dp = [[0]*(n+1) for _ in range(m+1)]
            for i in range(m+1):
                    dp[i][0] = i
            for j in range(n+1):
                    dp[0][j] = j
            for i in range(1, m+1):
                for j in range(1, n+1):
                    if word1[i-1] == word2[j-1]:
                        dp[i][j] = dp[i-1][j-1]
                        dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
            return dp[m][n]

Log in to reply

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