代码随想录算法训练营

Day45 代码随想录算法训练营第 45 天 |LeetCode 115.不同的子序列 LeetCode583. 两个字符串的删除操作 LeetCode72. 编辑距离

---

---

前言

LeetCode 115.不同的子序列

讲解文档

LeetCode583. 两个字符串的删除操作

讲解文档

LeetCode72. 编辑距离

讲解文档

---

一、LeetCode115.不同的子序列

1.题目链接

LeetCode115.不同的子序列

2.思路

（1）dp[i][j] ：t[0,j]在S[0,i]的范围内，出现多少次
（2）状态转移方程
1）s[i] == t[j] ：s[i] 和 t[j] 都可以加入子串
出现次数包括两部分
① 用s[i] 对t[j]进行匹配：
s[i] 对t[j]进行匹配，那么只需要在S[0,i-1]中t[0,j-1]进行匹配，
t[0,j]在S[0,i]的范围内出现次数等于t[0,j-1]在S[0,i-1]中出现次数
②不用s[i] 对t[j]进行匹配：t[0,j]在S[0,i]的范围内出现次数等于t[0,j]的子串在S[0,i-1]的子串出现次数
2）s[i] ！= t[j]：s[i] 不可以加入子串
不能用s[i] 对t[j]进行匹配：t[0,j]在S[0,i]的范围内出现次数等于t[0,j]的子串在S[0,i-1]的子串出现次数

3.题解

class Solution {
public:long long numDistinct(string s, string t) {if (s.size() < t.size())return 0;vector<vector<long long>> dp(s.size(), vector<long long>(t.size(), 0));if (s[0] == t[0])dp[0][0] = 1;for (int i = 1; i < s.size(); i++) {if (s[i] == t[0]) {dp[i][0] = (1 + dp[i - 1][0]);} else {dp[i][0] = dp[i - 1][0];}}for (int i = 1; i < s.size(); i++) {for (int j = 1; j < t.size(); j++) {if (s[i] == t[j])dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];elsedp[i][j] = dp[i - 1][j];dp[i][j] %= (1000000000 + 7);}}return dp[s.size() - 1][t.size() - 1];}
};

二、LeetCode583. 两个字符串的删除操作

1.题目链接

LeetCode583. 两个字符串的删除操作

2.思路

（1）dp[i][j]：将word1[0,i] word2[0,j]变成一样所需的步骤
（2）状态转移：
1）word1[i] == word2[j]：只需要将word1[0,i-1] word2[0,j-1]变成一样
2）word1[i] ！= word2[j]：
① 删word1[i]：word1[0,i-1] word2[0,j]变成一样需要删的元素+1
②删word2[j]：word1[0,i] word2[0,j-1]变成一样需要删的元素+1
③ 删word1[i]和word2[j]：word1[0,i-1] word2[0,j-1]变成一样需要删的元素+2
由于③可以看作①或②得到的，所以不考虑
（3）初始化
1）i=0：
只要出现过word1[0] 等于word2[j]，那么此后需要删除的元素数为j （因为word2除了word2[j]以外的元素有j个）
在出现之前，需要删除的元素数为j+2 （要删除word1[0]和word2里面j+1个元素）
2）j=0：
只要出现过word1[i] 等于word2[0]，那么此后需要删除的元素数为i （因为word1除了word1[i]以外的元素有j个）
在出现之前，需要删除的元素数为i+2 （要删除word2[0]和word1里面i+1个元素）

3.题解

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n, vector(m, 0));int flag = 0;for (int i = 0; i < n; i++) {if (word1[i] == word2[0])flag = 1;if (flag)dp[i][0] = i;elsedp[i][0] = i + 2;}flag = 0;for (int i = 0; i < m; i++) {if (word1[0] == word2[i])flag = 1;if (flag)dp[0][i] = i;elsedp[0][i] = i + 2;}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (word1[i] == word2[j]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);}}}return dp[n - 1][m - 1];}
};

三、LeetCode72. 编辑距离

1.题目链接

LeetCode72. 编辑距离

2.思路

（1）dp[i][j]：将word1[0,i] 变成word2[0,j]所需的最少步骤
（2）状态转移：
1）word1[i] == word2[j]：只需要将word1[0,i-1] 变成word2[0,j-1]
2）word1[i] ！= word2[j]：
① 删word1[i]：word1[0,i-1] 变成word2[0,j]需步骤+1
②添加word2[j]：word1[0,i] 变成word2[0,j-1]需要步骤+1
③ word1[i] 替换为 word2[j]：word1[0,i-1] 变成word2[0,j-1]需要步骤+1
由于③可以看作①或②得到的，所以不考虑
（3）初始化
1）i=0：
只要出现过word1[0] 等于word2[j]，那么此后需要删除的元素数为j （因为word2除了word2[j]以外的元素有j个）
在出现之前，需要改变的元素数为j+1 （要将word1变为word2里面j+1个元素）
2）j=0：
只要出现过word1[i] 等于word2[0]，那么此后需要删除的元素数为i （因为word1除了word1[i]以外的元素有j个）
在出现之前，需要删除的元素数为i+1 （要将word2变成word1里面i+1个元素）

3.题解

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();if (n == 0)return m;if (m == 0)return n;vector<vector<int>> dp(n, vector<int>(m, 0));int flag = 0;for (int i = 0; i < n; i++) {if (word1[i] == word2[0])flag = 1;if (flag)dp[i][0] = i;elsedp[i][0] = i + 1;}flag = 0;for (int i = 0; i < m; i++) {if (word1[0] == word2[i])flag = 1;if (flag)dp[0][i] = i;elsedp[0][i] = i + 1;}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (word1[i] == word2[j])dp[i][j] = dp[i - 1][j - 1];else {dp[i][j] =min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;}}}return dp[n - 1][m - 1];}
};

---