当前位置：首页 > news >正文

代码随想录打卡第五十八天|● 583. 两个字符串的删除操作 ● 72. 编辑距离

news 2025/7/15 10:31:31

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

题目： 给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。
在这里插入图片描述

题目链接： 583. 两个字符串的删除操作
解题思路：
dp数组的含义：w1[:i-1]与w2[:j-1]相同的最小删除次数
比较当前字母
如果两个字母相同，则不用进行删除操作
即dp[i][j]=dp[i-1][j-1]
如果两个字母不同，要么删除w1 要么删除w2 要么两者都删取三者最小值
即dp[i][j]=max(dp[i-1][j]+1(删1),dp[i][j-1]+1(删2),dp[i-1][j-1]+2(都删)) 后面的+1和+2是删除的操作次数
代码如下：

class Solution {public int minDistance(String word1, String word2) {//相同 不删 dp[i][j]=dp[i-1][j-1];//不同 删1  删2 都删 dp[i][j]=max(dp[i-1][j]+1(删1),dp[i][j-1]+1(删2),dp[i-1][j-1]+2(都删))int[][] dp=new int[word1.length()+1][word2.length()+1];//初始化int temp=0;for(int i=0;i<=word1.length();i++){dp[i][0]=temp;temp++;}temp=0;for(int j=0;j<=word2.length();j++){dp[0][j]=temp;temp++;}for(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);}}}return dp[word1.length()][word2.length()];}
}

72. 编辑距离（重点复习）

题目： 给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
在这里插入图片描述
题目链接： 72. 编辑距离
解题思路：
相同时不变即 dp[i][j]=dp[i-1][j-1];
不同时取三种操作的最小值 dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
删除w1和添加w2是逆操作删除w2与添加w1是逆操作所以写删除或添加即可这里写删除操作
改操作 dp[i-1][j-1]+1 将 i，j改成相同的值
代码如下

class Solution {public int minDistance(String word1, String word2) {//相同时 不变//不同时 取三种操作的最小值//删除w1和添加w2是逆操作 删除w2与添加w1是逆操作 所以写删除或添加即可 这里写删除操作//改 dp[i-1][j-1]+1 将 i，j改成相同的值int[][] dp=new int[word1.length()+1][word2.length()+1];//初始化int temp=0;for(int i=0;i<=word1.length();i++){dp[i][0]=temp;temp++;}temp=0;for(int j=0;j<=word2.length();j++){dp[0][j]=temp;temp++;}for(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);}}}return dp[word1.length()][word2.length()];}
}