有关电子商务网站建设的 论文,仓库常用erp系统,网站上推广游戏怎么做,如何在局域网建立网站583. 两个字符串的删除操作
题目#xff1a; 给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。
题目链接#xff1a; 583. 两个字符串的删除操作 解题思路#xff1a; dp数组的含义 给定两个单词 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[][] dpnew int[word1.length()1][word2.length()1];//初始化int temp0;for(int i0;iword1.length();i){dp[i][0]temp;temp;}temp0;for(int j0;jword2.length();j){dp[0][j]temp;temp;}for(int i1;iword1.length();i){for(int j1;jword2.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 将 ij改成相同的值 代码如下
class Solution {public int minDistance(String word1, String word2) {//相同时 不变//不同时 取三种操作的最小值//删除w1和添加w2是逆操作 删除w2与添加w1是逆操作 所以写删除或添加即可 这里写删除操作//改 dp[i-1][j-1]1 将 ij改成相同的值int[][] dpnew int[word1.length()1][word2.length()1];//初始化int temp0;for(int i0;iword1.length();i){dp[i][0]temp;temp;}temp0;for(int j0;jword2.length();j){dp[0][j]temp;temp;}for(int i1;iword1.length();i){for(int j1;jword2.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()];}
}
