文章目录
题目
'''
Description: 583.两个字符串的删除操作
Autor: 365JHWZGo
Date: 2021-12-22 10:40:11
LastEditors: 365JHWZGo
LastEditTime: 2021-12-22 12:51:30
'''
思路
这道题本质上就是找最长子序列,然后用两个字符串的长度前去公共子序列的两倍就是这道题的答案,要看破表面,抓住重点。
思路请参考
718.最长重复子数组
代码
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
dp = [[0 for _ in range(len(word1)+1)]for _ in range(len(word2)+1)]
for i in range(1, len(word2)+1):
for j in range(1, len(word1)+1):
if word1[j-1] == word2[i-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)-2*dp[-1][-1]
运行结果
总结
还是那句老话,你要做到的不只是会这一道题,而是通过一道题会所有题,万变不离其宗,动态规划就是这么厉害。