摘要
- 套用“最长公共子序列”的思路，LeetCode392 判断子序列可以转化为：求s和t的最长公共子序列的长度，并判断这个最长公共子序列的长度是否和s的长度相等。
- LeetCode115 不同的子序列的dp数组的初始化非常重要，要回顾dp数组的定义，正确的进行初始化。
- 长度为0的字符串、dp数组的下标为0等情况要仔细考虑。
LeetCode392 判断子序列
双指针
- 不考虑动态规划的话，这道题目可以使用双指针法简单地解决。
class Solution {
public:
bool isSubsequence(string s, string t) {
int slow = 0;
for (int fast = 0; fast < t.size(); fast++) {
if (s[slow] == t[fast]) slow++;
if (slow >= s.size()) break;
}
return slow == s.size();
}
};
时间复杂度为 ，至少要遍历一次
t。
空间复杂度为 ，只需要维护快慢两个指针的位置。
为了便于对比，将使用动态规划思路的题解代码也在这里放一份。
动态规划
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 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] + 1;
else dp[i][j] = dp[i][j - 1];
}
}
return dp[s.size()][t.size()] == s.size();
}
};
时间复杂度为 ，与
s和t的size有关，两层循环。
空间复杂度为 ，需要维护一个二维的
dp数组。可以用滚动数组优化到 。
这道题目可以看成“编辑距离”类型的题目的入门题目，只需要考虑从
t中删除元素来得到s，不需要考虑增加或替换元素。实际上，如果套用“最长公共子序列”的思路，这道题目就可以转化为：求
s和t的最长公共子序列的长度，并判断这个最长公共子序列的长度是否和s的长度相等。dp数组及数组下标的含义：dp[i][j]表示，s的子序列中的元素的下标属于[0, i-1]，t的子序列中的元素的下标属于[0, j-1]，这两个子序列相等时的最长长度为dp[i][j]。-
递推公式，
dp[i][j]的更新有两种可能- 如果
s[i - 1] == t[j - 1]，说明当前比对到的字符可以接在已知的公共子序列后，根据dp数组的定义，新增字符前的最长公共子序列的长度为dp[i - 1][j - 1]，公共子序列新增字符s[i - 1]（t[j - 1]），则长度+1， - 如果
s[i - 1] != t[j - 1]，说明需要从t中删除t[j - 1]来得到s（不一定要真正的删除，只是模拟删除的过程），相当于不选取t[j - 1]进入最长公共子序列，那么根据dp数组的定义，比对过了t[j - 1]而不选取，相当于已知的公共子序列不变，
- 如果
初始化
dp数组，dp[i][0]和dp[0][j]都应该初始化成0，相当于没有比对任何字符，任何字符串和空字符串的最长公共子序列的长度都是0。遍历顺序，
i和j都是从小到大遍历。
题解代码
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 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] + 1;
else dp[i][j] = dp[i][j - 1];
}
}
return dp[s.size()][t.size()] == s.size();
}
};
- 这道题目，只需要知道在主序列（较长的序列
t）中是否存在子序列s，不需要知道存在多少个子序列s，不需要知道有多少种从主序列中删除元素的方法能够得到s。所以只需要比对长度。下一题就需要求出有多少种从主序列中删除元素的方法能够得到子序列，比较复杂。
以s = "abc", t = "ahbgdc"为例，模拟dp数组的更新过程。
LeetCode115 不同的子序列
这道题目和上一道题类似，但是 LeetCode 给出的难度分类一下子从简单变成了困难。
dp数组不能是最长公共子序列的长度了，只保存长度的信息是不够的，dp数组应该保存从主序列中选出目标子序列的方法种数。dp数组及数组下标的含义：dp[i][j]表示的是，从主序列s中尝试选出一个子序列，其中元素的下标属于[0, i-1]，从目标序列t中尝试选出一个子序列，其中元素的下标属于[0, j-1]，使得这两个子序列相等的选取方法的种数。-
递推公式，
dp[i][j]有两种更新的可能- 如果
s[i - 1] == t[j - 1]，说明可以选取s[i - 1]，- 但是不一定选取
s[i - 1]，因为在s[i - 1]前后可能还有s[i - k]或s[i + k]与t[j - 1]相等，所以不一定选取s[i - 1]，那么尝试过了s[i - 1]但不选取，保留之前的状态，之前已知的不选取s[i - 1]方法种数是dp[i - 1][j] - 如果选取
s[i - 1]，s[i - 1] == t[j - 1]是固定的选取方式，就一种，只要看之前的子序列有多少种相等的可能，之前已知的方法种数是dp[i - 1][j - 1] - 那么，比对完
s[i - 1]和t[j - 1]之后，已知选取的方法种数是以上两种情况之和
- 但是不一定选取
- 如果
s[i - 1] != t[j - 1]，说明不可以选取s[i - 1]- 尝试过了
s[i - 1]但不选取，自然是保留之前的状态，之前能选取出公共子序列但不选取s[i - 1]的方法种数是dp[i - 1][j]，所以
- 尝试过了
- 如果
-
初始化
dp数组，这道题目的dp初始化非常重要，初始化dp数组时，除了要保证初始值不会阻碍递推公式更新dp数组以外，也要回顾dp数组的定义。- 先看
dp[0][j]，根据dp数组的定义，主序列s的长度是0，即主序列s中没有任何元素，没有任何元素可以选取，当然无法选取出一个子序列和目标序列t相等，所以dp[0][j]=0 - 再看
dp[i][0]，根据dp数组的定义，主序列s的长度是i，但是目标序列t的长度是0即目标序列t是空序列，所以在主序列s中选取0个元素就可以得到目标序列t，选取0个元素也就是不选取任何元素，方法种数是1。所以dp[i][0]=1 - 那
dp[0][0]初始化成0还是1呢？还是看dp数组的定义，主序列s的长度是0，没有任何元素可以选取，但是目标序列t的长度也是0，不需要从主序列中选取任何元素即可得到目标序列t。所以dp[0][0]=1。
- 先看
遍历顺序：
i，j都从小到大遍历
题解代码如下
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
for (int i = 0; i <= s.size(); i++) {
dp[i][0] = 1;
}
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()];
}
};
以s = "babgbag", t = "bag"为例，模拟dp数组的更新过程
