力扣115:不同的子序列

题目

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

思路

首先我们来考虑特殊情况，当s串的长度小于t串时s串肯定就没有t串了。其他情况我们就需要想一想怎么做了，如果按照暴力做法我们就遍历s串先找到t串的第一个字符然后再找第二个第三个，也就是一个一个字符的匹配，问题是题目设置的是s串的子序列而不是子串，子序列是不需要连续的所以这就导致找到了第一个字符后可能会有很多个第二个字符也就导致我们的时间复杂度会很高。那么我们是否可以换一种思想，既然是要一个一个的匹配也就是我们可以把两个字符串拆分成一个一个的字符，我们定义一个二维数组dp，设s串的下标为i，t串的下标为j。我们设dp[i][j]是s[i,…]也就是i位置到末尾的s子串种t[j,…]即j到末尾的t子串的数量，简单来说我们就是把这个问题分成了一个一个的子问题，我们利用这个二维数组来移动i和j从而得到不同的s子串中不同的t子串出现的个数。然后再找寻其中的规律推导出状态转移方程出来，所以我们是利用了动态规划的思想，把大问题分成小问题。
那么这个二维数组dp我们要如何定义呢？我们需要定义成一个(n+1)*(m+1)的，n为s串的长度m为t串的长度。为什么要+1呢因为我们需要我们从这两个子串是空串的情况开始，当s为空串t不为空串时dp[i][j] = 0因为一个空串里怎么可能有非空串，当s为非空串t为空串时dp[i][j] =1因为一个空串是任意一个非空串的子序列。所以dp[i][0] = 1( 0 <= i <= n)。在对特殊情况进行讨论后我们现在就要移动i和j来得到每一个子问题的答案了，这里需要分成两种情况。

1. s[i-1] == t[j-1]
   当此位置的字符相同时，我们需要考虑一个问题那就是这个字符是需要匹配的吗，这是什么意思呢。我们还需要回顾一下题目说的是s串的子序列中t出现的个数，是子序列所以不是连续的所以在这两个相等的字符前面可能还有和t[j]相同的s[i]，所以我们需要讨论这两种情况例如s:tbabag,t:bag。s的第一个a不是一定要和t的a进行匹配的也可以让后面那个a来和t的a进行匹配，这就是为什么要考虑是否需要匹配。如果两个字符匹配了那么此时的dp[i][j] = dp[i-1][j-1],也就是我们需要考虑t[j-1,…]作为s[i-1,…]的子序列的情况了，如果不匹配此时的dp[i][j] = dp[i-1][j]，因为不匹配也就是这个i被跳过了我们就需要考虑t[j]作为s[i-1]的子序列的情况了。
2. s[i]-1 != t[j-1]
   如果两个字符不同就说明无法匹配,dp[i][j] = dp[i+1][j]。

代码

class Solution {
public:int numDistinct(string s, string t) {int n = s.length();int m = t.length();if (n < m) {return 0;}//dp[i][j]代表t中从0到j的子串作为s中从0到i的子串的子序列的个数vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(m + 1));for (int i = 0; i <= n; i++) {dp[i][0] = 1;}for (int i = 1; i <= n; i++) {char si = s[i-1];for (int j = 1; j <= m; j++) {char tj = t[j-1];if (si == tj) {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];} else {dp[i][j] = dp[i - 1][j];}}}return dp[n][m];}
};