583.两个字符串的删除操作

文章目录

题目

'''
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]

运行结果

583.两个字符串的删除操作

总结

还是那句老话,你要做到的不只是会这一道题,而是通过一道题会所有题,万变不离其宗,动态规划就是这么厉害。

上一篇:c语言 13 - 5


下一篇:模块基础