题目
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例
示例
输入： “sea”, “eat”
输出： 2
解释： 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
关键思路
可以先求出两个字符串的最长公共字串，我们用到动态规划的思想进行求解。
代码实现
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
dp = [ [0 for m in range(len(word1)+1) ] for n in range(len(word2)+1) ]
for i in range(1,len(word2)+1):
for j in range(1,len(word1)+1):
if word2[i-1]==word1[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return len(word1)+len(word2)-dp[-1][-1]*2
运行结果
总结反思
多找到题目中的相同点，可以举一反三。
链接
https://leetcode-cn.com/problems/delete-operation-for-two-strings