网站建设gzzhixun,河北住房和城乡建设厅网站电话是多少,工业外观设计,qq网页版在线登录官方编辑距离问题
题目关键点115. 不同的子序列 - 力扣#xff08;LeetCode#xff09;*dp数组定义#xff0c;情况讨论583. 两个字符串的删除操作 - 力扣#xff08;LeetCode#xff09;两个字符串删除#xff0c;情况讨论多加一种72. 编辑距离 - 力扣#xff08;LeetCode…编辑距离问题
题目关键点115. 不同的子序列 - 力扣LeetCode*dp数组定义情况讨论583. 两个字符串的删除操作 - 力扣LeetCode两个字符串删除情况讨论多加一种72. 编辑距离 - 力扣LeetCode删除 添加 、替换操作115. 不同的子序列 - 力扣LeetCode 确定dp数组dp table以及下标的含义 dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。 这样定义注定s中要删除元素满足t的条件。比如s:baggt:bag那么就需要s中删除元素满足t的条件。 本题刚开始的dp数组定义就与之前子序列的定义不同所以分析方法也不同。 确定递推公式这一类问题基本是要分析两种情况 s[i - 1] 与 t[j - 1]相等时dp[i][j]可以有两部分组成。 一部分是用s[i - 1]来匹配那么个数不变还是看上一个序列的个数dp[i - 1][j - 1]。-一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。因为s序列中可能出现重复的部分。 例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。 s[i - 1] 与 t[j - 1] 不相等 dp[i][j]只有一部分组成不用s[i - 1]来匹配就是模拟在s中删除这个元素即dp[i - 1][j] 所以递推公式为dp[i][j] dp[i - 1][j]; dp数组如何初始化 从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来那么dp[i][0]和dp[0][j]是一定要初始化的。 dp[i][0] 表示以i-1为结尾的s可以随便删除元素出现空字符串的个数。那么dp[i][0]一定都是1因为把以i-1为结尾的s删除所有元素出现空字符串的个数就是1。 dp[0][j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0s如论如何也变成不了t。 dp[0][0]应该是1空字符串s可以删除0个元素变成空字符串t。 遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。 class Solution {public int numDistinct(String s, String t) {int m s.length();int n t.length();int [][] dp new int [m 1][n 1];//dp数组的初始化for(int i 1 ; i m ; i ){dp[i][0] 1;}for(int i 1 ; i n ; i ){dp[0][i] 0;}dp[0][0] 1;for(int i 1 ; i m ; i ){char s1 s.charAt(i - 1);for(int j 1 ; j n ; j ){char t1 t.charAt(j - 1);//s1 t1 存在两种情况不用s[i - 1]匹配 用s[i - 1]匹配if(s1 t1) dp[i][j] dp[i - 1][j] dp[i - 1][j - 1];//s1 ! t1 只有一种情况不用s[i - 1]匹配。else dp[i][j] dp[i - 1][j];// System.out.println(以s[ (i - 1) ]结尾的字符串中以t[ (j - 1) ]结尾的子序列的个数为 dp[i][j]);}}return dp[m][n];}
}583. 两个字符串的删除操作 - 力扣LeetCode dp定义dp[i][j]以i - 1结尾的word1和以j - 1结尾的word2删除字符后使两个单词相等的最小删除步数为dp[i][j]。 dp数组推导 word1[i - 1] word2[j - 1]不需要删除dp[i][j] dp[i - 1][j - 1]。 word1[i - 1] ! word2[j - 1]需要删除删除word1或删除word2dp[i][j] Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1) dp[i - 1][j]此时dp数组的定义为以i - 2结尾的word1和以j - 1结尾的word2删除字符后使两个单词相等的最小删除步数。 相当于从dp数组定义上删除了i - 1这个字符。 初始化dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。dp[0][j]的话同理。 遍历顺序从前往后从上往下遍历。 举例推导dp class Solution {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 0 ; i m ; i ){dp[i][0] i;}for(int j 0 ; j n ; j ){dp[0][j] j;}for(int i 1 ; i m ; i ){char w1 word1.charAt(i - 1);for(int j 1 ; j n ; j ){char w2 word2.charAt(j - 1);if(w1 w2) dp[i][j] dp[i - 1][j - 1];else dp[i][j] Math.min(dp[i - 1][j] 1 , dp[i][j - 1] 1);//System.out.println(以word1[ (i - 1) ]和word[ (j - 1) ]结尾的单词最少需要 dp[i][j] 步删除才能使word1与word2相等);}}return dp[m][n];}
}72. 编辑距离 - 力扣LeetCode dp[i][j]以i - 1结尾的word1和以j - 1结尾的word2转换所需的最小操作数为dp[i][j]。 word1[i - 1] word2[j - 1] 不需要进行操作dp[i][j] dp[i - 1][j - 1]。 word1[i - 1] ! word2[j - 1]需要进行操作 删除添加word2删除一个元素相当于word1添加一个元素。 word1删除一个元素dp[i][j] dp[i - 1][j] 1。 word2删除一个元素word1添加元素dp[i][j] dp[i][j - 1] 1 替换可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是 dp[i][j] dp[i - 1][j - 1] 对吧。 那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] dp[i - 1][j - 1] 1; 这里的替换操作不需要考虑具体细节只需要想替换操作就是把不同的数替换为相同的数比相同时的操作要多一步。 dp数组初始化dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。 那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i; 同理dp[0][j] j; 从上往下从左往右遍历。 举例推导dp数组 class Solution {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 0 ; i m ; i ){dp[i][0] i;}for(int j 0 ; j n ; j ){dp[0][j] j;}for(int i 1 ; i m ; i ){char w1 word1.charAt(i - 1);for(int j 1 ; j n ; j ){char w2 word2.charAt(j - 1);if(w1 w2) dp[i][j] dp[i - 1][j - 1];else dp[i][j] Math.min(dp[i - 1][j - 1] 1 , Math.min(dp[i - 1][j] 1 , dp[i][j - 1] 1));//System.out.println(以word1[ (i - 1) ]和word2[ (j - 1) ]结尾的单词word1最少需要 dp[i][j] 步操作才能使word1与word2相等);}}return dp[m][n];}
}总结
392. 判断子序列 - 力扣LeetCode对比1143T1143是两个字符串都可以删元素而本题如果删元素是删除字符串t因为只有t有多余的字符串。115. 不同的子序列 - 力扣LeetCode与392. 判断子序列 - 力扣LeetCode类似也是删除元素并且只能删除其中有多余字符的字符串。不同的是在s[i - 1]与t[i - 1]相等时也要考虑不使用s[i - 1]的情况。583. 两个字符串的删除操作 - 力扣LeetCode与1143题思路基本一致。1143题的本质也是删除字符串。72. 编辑距离 - 力扣LeetCode比起删除多了一步替换的操作根据word1[i - 1] word2[j - 1]推导而来很巧妙。
