package LeetCode.DPpart16; /** * 583. 两个字符串的删除操作 * 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 * 每步 可以删除任意一个字符串中的一个字符。 * */ public class DeleteOperationforTwoStrings_583 { 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; } }
package LeetCode.DPpart16; /** * 72. 编辑距离 *给你两个单词 word1 和 word2, 请返回将word1转换成word2 所使用的最少操作数 。 * 你可以对一个单词进行如下三种操作: * 插入一个字符 * 删除一个字符 * 替换一个字符 * */ public class EditDistance_72 { 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-1 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]), dp[i - 1][j]) + 1; } } } return dp[m][n]; } }
标签:583,int,part16,word1,72,word2,String From: https://www.cnblogs.com/lipinbigdata/p/17481661.html