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

代码随想录算法训练营第56天 | 583、72

news 2025/6/27 4:08:29

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

题目描述

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。
示例1：
输入： $w or d 1 = " se a ", w or d 2 = " e a t "$
输出： $2$
示例2：
输入： $w or d 1 = " l ee t co d e ", w or d 2 = " e t co "$
输出： $4$

思路

1、确定dp数组
dp[i][j]表示以i-1为结尾的字符串word1和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数
2、确定递推公式
当word[i-1]和word2[j-1]相等时，直接等于上一状态即可
不相等时，存在三种情况：
1）删word1[i-1]
2）删word2[j-1]
3）同时删word1[i-1]和word2[j-1]
最后取最小值

解法

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1+1][len2+1];for(int i = 1;i<= len1;i++){for(int j = 1;j<=len2;j++){if(word1.charAt(i-1) == word2.charAt(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]);}}}return len1+len2-dp[len1][len2]*2;}
}

总结

好好看，好好学

72. 编辑距离

题目描述

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例1：
输入： $w or d 1 = " h orse ", w or d 2 = " ros "$
输出： $3$
示例2：
输入： $w or d 1 = " in t e n t i o n ", w or d 2 = " e x ec u t i o n "$
输出： $5$

思路

1、确定dp数组
dp[i][j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
2、确定递推公式
word1[i-1]和word2[j-1]
相等时，不进行操作
不相等时，可以进行增删改的动作

解法

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m+1][n+1];for(int i = 1;i<=m;i++){dp[i][0] = i;}for(int j = 1;j<=n;j++){dp[0][j] = j;}for(int i = 1;i<=m;i++){for(int j = 1;j<=n;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]),dp[i-1][j])+1;}}}return dp[m][n];}
}