代码随想录算法训练营第四十五天 | 115-不同的子序列、583-两个字符串的删除操作、72-编辑距离
LeetCode115 不同的子序列
题目链接：https://leetcode.cn/problems/distinct-subsequences/description/
文章讲解：https://programmercarl.com/0115.不同的子序列.html
视频讲解：https://www.bilibili.com/video/BV1fG4y1m75Q/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题实际要求的就是字符串s有多少种删除方式得到字符串t，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示以i-1为结尾的s中有以j-1为结尾的t的个数
- 确定递推公式
两种情况：
-
s[i-1] == t[j-1]时，dp[i][j]可由两部分组成，一部分是用s[i-1]来进行匹配，个数为dp[i-1][j-1]，即不需要考虑s串和t串的最后一位字母；另一部分是不用s[i-1]来匹配，相当于删除了该字符，个数为dp[i-1][j]
-
s[i-1] != t[j-1]时，dp[i][j]只由一部分组成，即不用s[i-1]来匹配，个数为dp[i-1][j]
- dp数组如何初始化
dp[i][0] = 1，母串有一种删除方法得到空字符串
dp[0][j] = 0，母串为空串，没有删除方法得到子串
- 确定遍历顺序
dp[i][j]由dp[i-1][j-1]、dp[i-1][j]推出，所以是从左到右，从上到下进行遍历
- 举例推导dp数组
class Solution {public int numDistinct(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];for(int i = 0; i <= s.length(); i++){dp[i][0] = 1;}for(int i = 1; i <= s.length(); i++){for(int j = 1; j <= t.length(); j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{dp[i][j] = dp[i-1][j];}}}return dp[s.length()][t.length()];}
}
LeetCode583 两个字符串的删除操作
题目链接：https://leetcode.cn/problems/delete-operation-for-two-strings/description/
文章讲解：https://programmercarl.com/0583.两个字符串的删除操作.html
视频讲解：https://www.bilibili.com/video/BV1we4y157wB/?vd_source=b989f2b109eb3b17e8178154a7de7a51
相较于LeetCode115 不同的子序列，本题两个字符串都可以进行删除操作，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示使得以i-1为结尾的word1和以j-1为结尾的word2相同的最少操作次数
- 确定递推公式
两种情况：
-
word1[i-1] == word2[j-1]时，word1的i-1处字符与word2的j-1处字符对相同化处理无影响，所以可以不考虑这两个元素，dp[i][j] = dp[i-1][j-1]
-
s[i-1] != t[j-1]时，要考虑这两个元素，分成三部分（w1w2都删、w1删w2不删、w1不删w2删）模拟，分别进行删减，dp[i][j] = Math.min(dp[i-1][j-1] + 2，Math.min(dp[i-1][j] + 1，dp[i][j-1] + 1)) 【又因为“dp[i-1][j-1]”可由“dp[i-1][j] + 1”或“dp[i][j-1] + 1”推导而来，所以该式又可简化为dp[i][j] = Math.min(dp[i-1][j] + 1，dp[i][j-1] + 1)】
- dp数组如何初始化
dp[i][0] = 1，word1需要进行i次删除得到空字符串
dp[0][j] = 0，word2需要进行j次删除得到空字符串
- 确定遍历顺序
dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]推出，所以是从左到右，从上到下进行遍历
- 举例推导dp数组
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(); i++){dp[i][0] = i;}for(int j = 0; 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(dp[i-1][j-1] + 2, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));}}}return dp[word1.length()][word2.length()];}
}
本题还有另外一种巧妙的思路，求word1和word2的最长公共子序列，不属于该最长公共子序列的元素就是最终需要删除的元素，最少操作次数= (word1长度 + word2长度) - 最长公共子序列长度*2，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示[0，i-1]的word1和[0，j-1]的word2，二者的最长公共子序列的长度
- 确定递推公式
如果word1[i-1] == word2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1
如果word1[i-1] != word2[j-1]，那么dp[i][j] = Math.max(dp[i-1][j]，dp[i][j-1]）
- dp数组如何初始化
与空字符串比较无公共子序列，故第零行和第零列都初始化为0
- 确定遍历顺序
由递推公式dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]得出，故两层for循环都是从1开始顺序遍历到word1.length/word2.length
- 举例推导dp数组
class Solution {public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length()+1][word2.length()+1];int target = 0;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] + 1;}else{dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}target = Math.max(target, dp[i][j]);}}return word1.length() + word2.length() - target*2;}
}
LeetCode72 编辑距离
题目链接：https://leetcode.cn/problems/edit-distance/
文章讲解：https://programmercarl.com/0072.编辑距离.html
视频讲解：https://www.bilibili.com/video/BV1qv4y1q78f/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题是要求从word1通过增删改的最少操作数得到word2，对word2进行增相当于对word1进行删，对word2进行改相当于对word1进行改，对word2进行删相当于对word1进行增，所以大致思路是类似于LeetCode583 两个字符串的删除操作，细节上有所区别，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示将以i-1为结尾的word1转换成以j-1为结尾的word2的最少操作次数
- 确定递推公式
两种情况：
-
word1[i-1] == word2[j-1]时，word1的i-1处字符与word2的j-1处字符对相同化处理无影响，所以可以不考虑这两个元素，dp[i][j] = dp[i-1][j-1]
-
s[i-1] != t[j-1]时，要考虑这两个元素，分成三部分（改：w1改成w2、删：w1删w2不删、增：w1不删w2删）模拟，分别进行删减，dp[i][j] = Math.min(dp[i-1][j-1] + 1，Math.min(dp[i-1][j] + 1，dp[i][j-1] + 1))
- dp数组如何初始化
dp[i][0] = 1，word1需要进行i次删除得到空字符串
dp[0][j] = 0，word2需要进行j次删除得到空字符串
- 确定遍历顺序
dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]推出，所以是从左到右，从上到下进行遍历
- 举例推导dp数组
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(); i++){dp[i][0] = i;}for(int j = 0; 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(dp[i-1][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));}}}return dp[word1.length()][word2.length()];}
}