Share my Python DP solution


  • 0
    A
    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]
                    else:
                        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.