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];}
}

总结

编辑距离似乎前两天刚刷过