LeetCode刷题实战583两个字符串的删除操作

　　算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！
　　今天和大家聊的问题叫做两个字符串的删除操作，我们先来看题面：
　　https：leetcodecn。comproblemsdeleteoperationfortwostringsGiventwostringsword1andword2，returntheminimumnumberofstepsrequiredtomakeword1andword2thesame。
　　Inonestep，youcandeleteexactlyonecharacterineitherstring。
　　给定两个单词word1和word2，返回使得word1和word2相同所需的最小步数。
　　每步可以删除任意一个字符串中的一个字符。示例示例1：
　　输入：word1sea，word2eat
　　输出：2
　　解释：第一步将sea变为ea，第二步将eat变为ea
　　示例2：
　　输入：word1leetcode，word2etco
　　输出：4解题
　　https：blog。csdn。nethequnwang10articledetails123941103
　　主要思路：动态规划
　　dp〔i〕〔j〕：表示要使word1和word2变成下标为i和j时相等的字符串需要最少的删除次数
　　初始化：
　　当word1字符串为空时，需要将word2字符串依次删除才可以：
　　dp〔0〕〔j〕j
　　同样的，当word2字符串为空时，需要将word1字符串依次删除才可以：
　　dp〔i〕〔0〕i
　　当两者都不为空时，从第一个字符开始遍历，要么两个字符相等，要么两个字符不相等：
　　两个字符相等时，直接与上一个状态相等
　　dp〔i〕〔j〕dp〔i1〕〔j1〕
　　两个字符不相等时，则由上一个状态转移，找最小的删除次数，然后1；
　　dp〔i〕〔j〕Math。min（dp〔i1〕〔j〕，dp〔i〕〔j1〕）1；classSolution｛
　　publicintminDistance（Stringword1，Stringword2）｛
　　intmword1。length，nword2。length；
　　intdpnewint〔m1〕〔n1〕；
　　当一个字符串为空时，如果需要两个字符串都相同，必须将另一个字符串全部删除
　　for（inti1；im；i）｛
　　dp〔i〕〔0〕i；
　　｝
　　当一个字符串为空时，如果需要两个字符串都相同，必须将另一个字符串全部删除
　　for（intj1；jn；j）｛
　　dp〔0〕〔j〕j；
　　｝
　　for（inti1；im；i）｛
　　charc1word1。charAt（i1）；
　　for（intj1；jn；j）｛
　　charc2word2。charAt（j1）；
　　如果两个字符串的字符相等，则最少删除次数不变。
　　if（c1c2）｛
　　dp〔i〕〔j〕dp〔i1〕〔j1〕；
　　｝else｛
　　如果两个字符串的字符不相等，则取两个字符串减一个后的最小值然后1。
　　dp〔i〕〔j〕Math。min（dp〔i1〕〔j〕，dp〔i〕〔j1〕）1；
　　｝
　　｝
　　｝
　　returndp〔m〕〔n〕；
　　｝
　　｝
　　在看或者转发吧，你们的支持是我最大的动力。
　　上期推文：
　　LeetCode1580题汇总，希望对你有点帮助！
　　LeetCode刷题实战581：最短无序连续子数组
　　LeetCode刷题实战582：杀掉进程