*算法训练（leetcode）第三十九天 | 115. 不同的子序列、583. 两个字符串的删除操作、72. 编辑距离

*115. 不同的子序列

leetcode题目地址

dp[i][j]代表：以i-1结尾的s中包含以j-1结尾的t的个数。

有以下两种情况：

• s[i-1] == t[i-1]：
  • 考虑s[i-1]
  • 不考虑s[i-1]
• s[i-1] != t[i-1]

题解思路

时间复杂度： $O(n^2)$
空间复杂度： $O(n\ast m)$

// c++
class Solution {
public:int numDistinct(string s, string t) {vector<vector<unsigned int>> dp(s.size()+1, vector<unsigned int>(t.size()+1, 0));dp[0][0] = 1;for(int i=1; i<=s.size(); i++){dp[i][0] = 1;}for(int i=1; i<=t.size(); i++){dp[0][i] = 0;}for(int i=1; i<=s.size(); i++){for(int j=1; j<=t.size(); j++){if(s[i-1] == t[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.size()][t.size()];}
};

*583. 两个字符串的删除操作

leetcode题目地址

解法一

dp[i][j]存储i-1结尾的word1与以j-1结尾的word2最少删除操作的次数。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

解法二

dp[i][j]存储i-1结尾的word1与以j-1结尾的word2最长公 共子序列。最后用word1.size()+word2.size()减去最长公共子序列。

// c++
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));for(int i=1; i<=word1.size(); i++){for(int j=1; j<=word2.size(); j++){if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);}}return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;}
};

*72. 编辑距离

leetcode题目地址

dp[i][j]存储i-1结尾的word1与以j-1结尾的word2最少操作的次数。

• word1[i-1] == word2[j-1]
  • 无需操作：dp[i][j] = dp[i-1][j-1]
• word1[i-1] != word2[j-1]
  • 增：（word1增、word2增、word1&word2都增）和删除等效
  • 删：（word1删：dp[i-1][j]+1、word2删：dp[i][j-1]+1、word1&word2都删：dp[i-1][j-1]+2）
  • 改：（仅需修改一次）dp[i-1][j-1] + 1

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

// c++
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));for(int i=0; i<=word1.size(); i++) dp[i][0] = i;for(int j=0; j<=word2.size(); j++) dp[0][j] = j;for(int i=1; i<=word1.size(); i++){for(int j=1; j<=word2.size(); j++){if(word1[i-1] == word2[j-1]){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;}}/*// 输出dpfor(int j=1; j<=word2.size(); j++) cout<<dp[i][j]<<" ";cout<<endl;*/}return dp[word1.size()][word2.size()];}
};