优秀国内个人网站网址,网站改版的宣传词,宝塔装wordpress,江门专业网站制作公司583. 两个字符串的删除操作 题目链接#xff1a;两个字符串的删除操作 题目描述#xff1a; 给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 解题思路#xff1a; 1、确定dp数组#x…583. 两个字符串的删除操作 题目链接两个字符串的删除操作 题目描述 给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 解题思路 1、确定dp数组dp table以及下标的含义 dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。 这里dp数组的定义有点点绕大家要撸清思路。 2、确定递推公式 当word1[i - 1] 与 word2[j - 1]相同的时候 当word1[i - 1] 与 word2[j - 1]不相同的时候 当word1[i - 1] 与 word2[j - 1]相同的时候dp[i][j] dp[i - 1][j - 1]; 当word1[i - 1] 与 word2[j - 1]不相同的时候有三种情况 情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1 情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1 情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2 那最后当然是取最小值所以当word1[i - 1] 与 word2[j - 1]不相同的时候递推公式dp[i][j] min({dp[i - 1][j - 1] 2, dp[i - 1][j] 1, dp[i][j - 1] 1}); 因为 dp[i][j - 1] 1 dp[i - 1][j - 1] 2所以递推公式可简化为dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1); 这里可能不少录友有点迷糊从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]dp[i][j-1] 本来就不考虑 word2[j - 1]了那么我在删 word1[i - 1]是不是就达到两个元素都删除的效果即 dp[i][j-1] 1。 3、dp数组如何初始化 从递推公式中可以看出来dp[i][0] 和 dp[0][j]是一定要初始化的。 dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。 dp[0][j]的话同理 代码实现
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、if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1]; 2、if (word1[i - 1] ! word2[j - 1])此时就需要编辑了。 操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] dp[i - 1][j] 1; 操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] dp[i][j - 1] 1; 操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增删加元素。 可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是 dp[i][j] dp[i - 1][j - 1] 对吧。 那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。 所以 dp[i][j] dp[i - 1][j - 1] 1; 综上当 if (word1[i - 1] ! word2[j - 1]) 时取最小的即dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 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) {// 因为dp数组有效位从1开始// 所以当前遍历到的字符串的位置为i-1 | j-1if (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];}
}
