Leetcode 72. Edit Distance

https://leetcode.com/problems/edit-distance/

A typical DP problem.

Solution:

# T:O(m*n) S:O(m*n)
class Solution:
    # @param {string} word1
    # @param {string} word2
    # @return {integer}
    def minDistance(self, word1, word2):
        m, n = len(word1)+1, len(word2)+1
        dp = [([0]*n) for i in xrange(m)]
        for i in xrange(n):
            dp[0][i] = i
        for i in xrange(m):
            dp[i][0] = i
        for i in xrange(1,m):
            for j in xrange(1,n):
                dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(1 if word1[i-1] != word2[j-1] else 0))
        return dp[m-1][n-1]

Run Time: 284 ms