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

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

题目描述

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例1：
输入：$word1="sea",word2="eat"$
输出：$2$
示例2：
输入：$word1="leetcode",word2="etco"$
输出：$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：
输入：$word1="horse",word2="ros"$
输出：$3$
示例2：
输入：$word1="intention",word2="execution"$
输出：$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];}
}

总结

最近考试周，没细看，我有罪，等考试周结束之后再好好总结