北京平台网站建设找哪家,做视频网站服务器配置,网站站内优化案例,镇江网站推广优化583. 两个字符串的删除操作 题目#xff1a;给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 思路#xff1a;这题思路主要是求出 word1 字符串和 word2 字符串中的最长相同的子字符串给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 思路这题思路主要是求出 word1 字符串和 word2 字符串中的最长相同的子字符串比如“abc”子字符串为“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”求出最长相同的字符串之后用两个字符串的长度和减去两倍的最长相同子字符串就是我们需要求得长度。 class Solution {public int minDistance(String word1, String word2) {int len1 word1.length();int len2 word2.length();int[][] dp new int[len11][len21];for(int i1;ilen1;i){for(int j1;jlen2;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 len1len2-2*dp[len1][len2];}
} 72. 编辑距离 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
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 0; i len1; i) {dp[i][0] i;}for (int i 0; i len2; i) {dp[0][i] i;}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];elsedp[i][j] Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) 1;//三种情况分别代表dp[i][j - 1]增加一个元素dp[i - 1][j]删除一个元素 dp[i - 1][j - 1]修改一个元素}}return dp[len1][len2];}
}
