一般网站的架构,个人网页制作成品下载,网站建设网络公,商城开发建设代码随想录训练营第56天|583.两个字符串的删除操作#xff0c;72.编辑距离 583.两个字符串的删除操作文章思路代码 72.编辑距离文章思路代码 总结 583.两个字符串的删除操作
文章
代码随想录|0583.两个字符串的删除操作
思路
如果不按照编辑距离考虑的话#xff0c;只需要… 代码随想录训练营第56天|583.两个字符串的删除操作72.编辑距离 583.两个字符串的删除操作文章思路代码 72.编辑距离文章思路代码 总结 583.两个字符串的删除操作
文章
代码随想录|0583.两个字符串的删除操作
思路
如果不按照编辑距离考虑的话只需要求最长相同子序列的长度l则word1.length()word2.length-2*l即为所求
代码
class Solution {public int minDistance(String word1, String word2) {int i, j, m, n;m word1.length();n word2.length();int[][] dp new int[m][n];for (i 0; i m; i) {for (j 0; j n; j) {if (i 0 j 0) {dp[i][j] word1.charAt(i) word2.charAt(j) ? 1 :0;} else if (i 0) {dp[i][j] word1.charAt(i) word2.charAt(j) ? 1 : dp[i][j - 1];} else if (j 0) {dp[i][j] word1.charAt(i) word2.charAt(j) ? 1 : dp[i - 1][j];} else {dp[i][j] word1.charAt(i) word2.charAt(j) ? (dp[i - 1][j - 1] 1) : Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return m n - 2 * dp[m - 1][n - 1];}
}72.编辑距离
文章
代码随想录|0072.编辑距离
思路
dp[i][j]表示Word1从0到i的部分与word2从0到j部分的编辑距离 显然如果word1[0]word2[0]则有dp[0][0]0否则为1 当比较到word1[i]和word2[j]时如果相等则dp[i][j]dp[i-1][j-1] 否则就是dp[i][j]Min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
代码
class Solution {public int minDistance(String word1, String word2) {int i, j, m, n;m word1.length();n word2.length();if (m 0 || n 0) {return Math.max(m, n);}int[][] dp new int[m][n];for (i 0; i m; i) {for (j 0; j n; j) {if (i 0 j 0) {dp[i][j] word1.charAt(i) word2.charAt(j) ? 0 : 1;} else if (i 0) {dp[i][j] word1.charAt(i) word2.charAt(j) ? j : dp[i][j - 1] 1;} else if (j 0) {dp[i][j] word1.charAt(i) word2.charAt(j) ? i : dp[i - 1][j] 1;} else {if (word1.charAt(i) word2.charAt(j)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) 1;}}}}return dp[m -1][n -1];}
}总结
编辑距离似乎前两天刚刷过
