外贸cms建站,宣传型商务网站,网站首页布局风格,域名和网站建设费如何入帐代码随想录第五十六天 Leetcode 583. 两个字符串的删除操作Leetcode 72. 编辑距离 Leetcode 583. 两个字符串的删除操作
题目链接: 两个字符串的删除操作 自己的思路:想到了#xff0c;但是初始化初始错了#xff01;#xff01;#xff01;#xff01;
思路1:直接动规五… 代码随想录第五十六天 Leetcode 583. 两个字符串的删除操作Leetcode 72. 编辑距离 Leetcode 583. 两个字符串的删除操作
题目链接: 两个字符串的删除操作 自己的思路:想到了但是初始化初始错了
思路1:直接动规五部曲1、dp数组的含义dp[i][j]表示以i-1和j-1为结尾的两个字符串的最少字符删除个数2、递推公式这里考虑两种情况1、当dp[i-1]dp[j-1]的时候两个元素的是相等的那么这两个元素就不用删所以说dp[i][j]还是等于dp[i-1][j-1]的2、当dp[i-1]!dp[j-1]的时候两个元素不相等这里就要考虑将其中一个元素删除掉如果删除s1[i-1]那么就是dp[i-1][j]1如果删除s2[j-1]那么就是dp[i][j-1]1如果两个都删的话那就是dp[i-1][j-1]23、dp数组的初始化这里由于某个点的值是由其左上角、上方、左方元素得到所以我们初始化的时候一定要初始化第一行和第一列拿第一行为例dp[0][j]也就是s1是空字符串s2非空那么删除的元素个数其实就是j的值第一列也同理4、遍历顺序前面说了由左上方三个元素确定所以一定是左到右上到下遍历5、打印dp数组主要用于debug
代码:
class Solution {public int minDistance(String word1, String word2) {char[] c1 word1.toCharArray();char[] c2 word2.toCharArray();int m c1.length;int n c2.length;int[][] dp new int[m1][n1];for (int i 0;im;i){dp[i][0] i;}for (int i 0;in;i){dp[0][i] i;}dp[0][0]0;for (int i 1;im;i){for (int j1;jn;j){//递推公式if (c1[i-1]c2[j-1]){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]1,dp[i-1][j-1]2));}}}return dp[m][n];}
}思路2:最长公共子序列的思路
代码:
class Solution {public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int[][] dp new int[m1][n1];for (int i 1;im;i){for (int j1;jn;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 mn-2*dp[m][n];}
}Leetcode 72. 编辑距离
题目链接: 编辑距离 自己的思路:思路差不多只是没调出来
正确思路:直接动规五部曲1、dp数组的含义以s1[i-1]结尾的s1和以s2[j-1]结尾的s2怎么操作才可以由s1变到s22、递推公式这里还是涉及两种情况1、s1[i-1]s2[j-1]这种情况下是不需要变元素的所以直接dp[i][j]dp[i-1][j-1]2、s1[i-1]!s2[j-1]这种情况下我们就需要做增删替换了我们可以将s1[i-1]删掉就变成了dp[i-1][j]1将s2[i-1]删掉就变成了dp[i][j-1]1这里其实是可以动s2的因为s1的增相当于s2的删s1的删相当于s2的增还有一种情况是替换的情况我们需要替换一个元素可以达到1的效果那么就是dp[i-1][j-1]13、dp数组初始化这里其实和上一题一样的初始化4、遍历同上5、打印dp数组主要用于debug
代码:
class Solution {public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int[][] dp new int[m1][n1];//初始化for (int i 0;im;i){dp[i][0] i;}for (int j0;jn;j){dp[0][j] j;}for (int i 1;im;i){for (int j1;jn;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,Math.min(dp[i][j-1]1,dp[i-1][j-1]1));}}}return dp[m][n];}
}
