LeetCode:583. 两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣（LeetCode）
1.思路
求公共子串，将两字符串长度之和减去2倍的公共子串的长度。
2.代码实现
// 求最长公共子串 class Solution { public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; for (int i = 1; i < word1.length() + 1; i++) { for (int j = 1; j < word2.length() + 1; 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 word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()]; } } // 直接求操作次数 class Solution { public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i; for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j; for (int i = 1; i <= word1.length(); i++) { for (int j = 1; j <= word2.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(dp[i - 1][j - 1] + 2, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)); } } } return dp[word1.length()][word2.length()]; } }
3.复杂度分析
LeetCode: 72. 编辑距离
1.思路
对于不同元素，添加和删除都是一步操作，替换是一步操作，动规状态转移方程的推导可以从左上、左侧、上侧来传递，对应的值要+1。
2.代码实现
class Solution { public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; for (int i = 1; i <= word1.length(); i++) { dp[i][0] = i; } for (int j = 1; j <= word2.length(); j++) { dp[0][j] = j; } for (int i = 1; i <= word1.length(); i++) { for (int j = 1; j <= word2.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], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } } return dp[word1.length()][word2.length()]; } }
3.复杂度分析
时间复杂度：O(n * m).
空间复杂度：O(n * m).
