115 不同的子序列

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit
示例 2：

输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

• 法一：二维动态规划

class Solution {
public:
    int numDistinct(string s, string t){
        int n=s.size(),m=t.size();
        if(n<m) return 0;//n是原串的字符数，m是子串的字符数，想在s中找到t，s的字符数一定要大于t的字符数
        //注意用例字符过多，此处只能使用unsigned long long
        //由于字符可以选择0个到n个，故dp数组长需要为n+1
        vector<vector<unsigned long long >> dp(n+1,vector<unsigned long long >(m+1,0));
        //边界，有两个。
        //第一行，原串s为空串，t有字符，此时s无法找到t，全部置0
        //第一列，原串有字符，t为空，此时s字符全部删除可以找到一种情况，全部置1
        for(int i=0;i<=n;i++)
            dp[i][0]=1;
        //填dp数组
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[i][j]+=dp[i-1][j];//情况一，不使用s[i-1]
                if(s[i-1]==t[j-1]) dp[i][j]+=dp[i-1][j-1];//情况二，使用s[i-1]且匹配成功
            }
        }
        return dp[n][m];//返回结果
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 时间复杂度O(n^2)

• 空间复杂度O(n^2)

• 思路

  • s是原串，t是子串，求从s找到t的方法数
  • dp[i][j]：s中1~i个字符中找到t中1 ~ j个字符的方法数
  • 状态转移方程:dp[i][j]=dp[i-1][j]+(s[i-1]==t[j-1]?dp[i-1][j-1]:0)
    • 分两种情况，s的第i个字符用或者不用。如果不用，则方法数与dp[i-1][j]相同；如果用，且s的第i个字符与t的第j个字符相同，则方法数与dp[i-1][j-1]相同。将两种情况得到的方法数加起来，就是所求的方法数

• 方法二：优化空间，一维动态规划

class Solution {
public:
    int numDistinct(string s, string t){
        int n=s.size(),m=t.size();
        if(n<m) return 0;
        //样例字符过多，只能选择unsigned long long
        vector<unsigned long long> dp(m+1,0);
        //pre记录当前未修改前的dp[j]对应二维dp中的dp[i-1][j],cur记录未修改前的dp[j-1]对应二维dp中的dp[i-1][j-1]
        int pre=0,cur=1;
        //填dp数组
        for(int i=1;i<=n;i++)
        {
            dp[0]=1;//类比到二维dp数组，初始化第一列为1，表示s非空t为空串的情况
            cur=1;//对于dp[1]而言，未修改前的dp[0]就是1
            //填当前行
            for(int j=1;j<=m;j++)
            {
                pre=dp[j];//记录未修改的dp[j]，为计算dp[j+1]做辅助
                //此处省略了情况一，即不选择s[i-1]，此时的dp[j]=dp[j]
                if(s[i-1]==t[j-1]) dp[j]+=cur;//情况二，选择s[i-1]
                cur=pre;//记录未修改前的dp[j],
            }
            
        }
        return dp[m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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