72. Edit Distance
哎，这么简单的题目都没做出来，有点想错了，一开始想成1维dp，然后就很不好做了。不过1维也是可以用滚动数组做的，很难理解就是了。有点做不动了，上午就到这吧。
class Solution(object):
def minDistance1(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
# O(m*n) space
l1, l2 = len(word1)+1, len(word2)+1
dp = [[0 for _ in xrange(l2)] for _ in xrange(l1)]
for i in xrange(l1):
dp[i][0] = i
for j in xrange(l2):
dp[0][j] = j
for i in xrange(1, l1):
for j in xrange(1, l2):
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(word1[i-1]!=word2[j-1]))
return dp[-1][-1]
# O(n) space with rolling array
def minDistance(self, word1, word2):
l1, l2 = len(word1)+1, len(word2)+1
dp = [0 for _ in xrange(l2)]
for j in xrange(l2):
dp[j] = j
for i in xrange(1, l1):
prev = i # when word1 is i length it will need i step to match word2 which is "" for now
for j in xrange(1, l2):
if word1[i-1] == word2[j-1]:
cur = dp[j-1]
else:
cur = min(dp[j-1], prev, dp[j]) + 1
dp[j-1] = prev
prev = cur
dp[l2-1] = prev
return dp[-1]
