题目
已知两个字符串word1和word2，求从word1转化成word2最少需要几步。其中，每一步只能进行以下三个操作之一：
- 插入一个字符
- 删除一个字符
- 替换一个字符
分析
用动态规划的思路，用dp[i][j]表示word1的前i个字符转化为word2的前j个字符需要的操作次数。根据word1和word2的最后一个字符是否相同，分为两种情况：
- word1[i] == word2[j]
那么同时去掉最后一个字符，不影响结果，故dp[i][j] = dp[i-1][j-1] - word1[i] != word2[j]
可以用如下三种方法进行操作：- 将word1转化为word2的前j-1个字符，再将word2的最后一个字符插入到word1末尾。即步骤为
dp[i][j-1]+1。 - 将word1的前i-1个字符转化为word2，再将word1的最后一个字符删除。即步骤为
dp[i-1][j]+1。 - 将word1的前i-1个字符转化为word2的前j-1个字符，再将word1的第i个字符替换为word2的第j个字符。即步骤为
dp[i-1][j-1]+1。
dp[i][j]为三种方法的最小值，即dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1)
- 将word1转化为word2的前j-1个字符，再将word2的最后一个字符插入到word1末尾。即步骤为
对于边界情况，i=0代表word1为空，故由word1插入j个字符可转化为word2，即dp[0][j] = j。同理，dp[i][0] = i
根据递推关系，这里不需要维护这个二维数组，只需要维护一行或者一列即可。
代码
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
dp = [i for i in range(len(word2) + 1)]
for i in range(1, len(word1)+1):
ndp = [i]
for j in range(1, len(dp)):
if word1[i-1] == word2[j-1]:
ndp.append(dp[j-1])
else:
ndp.append(min(dp[j-1]+1, dp[j]+1, ndp[j-1]+1))
dp = ndp
return dp[-1]
