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

LeetCode 583两个字符串的删除操作Delete Operation for Two Strings—— 题解 ✅ 题目链接 https://leetcode.cn/problems/delete-operation-for-two-strings/ 内容概要给定两个字符串word1和word2每一步可以对任意一个字符串删除一个字符。求使两个字符串完全相同所需的最少删除步数。✅ 只允许删除✅ 不允许插入、替换✅ 本质是最长公共子序列LCS的变形 解题思路核心一、关键转化最重要要让两个字符串相同最优策略是保留它们的最长公共子序列LCS。需要删除的字符数 len(word1) len(word2) − 2 × LCS二、DP 状态定义dp[i][j]将 word1 前 i 个字符 和 word2 前 j 个字符 变成相同所需的最少删除次数 状态转移重点讲解✅ 情况 1当前字符相同if(w1[i-1]w2[j-1]){dp[i][j]dp[i-1][j-1];}两个字符都保留不需要删除直接继承之前的结果❌ 情况 2当前字符不同有三种删除策略操作状态转移删除次数删除word1[i]和word2[j]dp[i-1][j-1] 2各删 1只删除word1[i]dp[i-1][j] 11只删除word2[j]dp[i][j-1] 11取最小值 ✅✅ AC 代码JavaclassSolution{publicintminDistance(Stringword1,Stringword2){char[]w1word1.toCharArray();char[]w2word2.toCharArray();intlen1word1.length();intlen2word2.length();int[][]dpnewint[len11][len21];// 初始化for(inti0;ilen1;i)dp[i][0]i;for(intj0;jlen2;j)dp[0][j]j;// 状态转移for(inti1;ilen1;i){for(intj1;jlen2;j){if(w1[i-1]w2[j-1]){dp[i][j]dp[i-1][j-1];}else{dp[i][j]Math.min(dp[i-1][j-1]2,// 两边都删Math.min(dp[i-1][j]1,// 删 word1[i]dp[i][j-1]1// 删 word2[j]));}}}returndp[len1][len2];}}⏱️ 复杂度分析指标复杂度时间复杂度O(len1 × len2)空间复杂度O(len1 × len2) 与 LCS 解法的关系解法思路LCS 解法先求公共子序列再算删除次数本题 DP直接建模删除代价两者结果完全等价dp[len1][len2] len1 len2 − 2 × LCS也可以直接用LCS代码来通过此题classSolution{publicintminDistance(Stringword1,Stringword2){char[]w1word1.toCharArray();char[]w2word2.toCharArray();intlen1word1.length();intlen2word2.length();int[][]dpnewint[len11][len21];intres0;for(inti1;ilen1;i){for(intj1;jlen2;j){if(w1[i-1]w2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]Math.max(dp[i-1][j],dp[i][j-1]);}resMath.max(res,dp[i][j]);}}returnlen1len2-2*res;}}