返回S子字符串等于T的不同子序列个数

---

题目描述

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，”ACE”is a subsequence of”ABCDE”但是”AEC”不是）
例如：

S =”rabbbit”, T =”rabbit”
返回3

解题思路

一般给出的字符串S的长度是大于或者等于字符串T的长度。

构造一个二维矩阵，行数为字符串T的长度+1，列数为字符串S的长度+1。加一的目的是考虑了两个字符串为零的情况。

当S字符串为0时，任何字符串T都含有一个满足条件的子序列。当T字符串为0时，对于任何长度不为0的字符串S来说，都没有满足条件的子序列。同时说明了T时S的子字符串。

对于非零的两个字符串进行如下比较。以题中给的例子解释以下。

首先初始化，第一行为1（T长度为0)；初始化第一列为0(S长度为0,T不为0时)。

保持子字符的第一个子字符串长度不变，依次递增S字符串字符。（即每行遍历数组）

• 若两个比较的字符不相同，则array[][] = array[i][j-1];(等于前面的数值)
• 若两个比较字符相同，则array[][] =array[i][j-1]+array[i-1][j-1]（等于前面的数值 加S子序列等于当前T'的子序列的个数）

当S中字符增加到最后一个字符时，则将T字符递增一个，然后继续递增S中的字符；继续如上循环直到结束。

代码

class Solution
{
public:
    int numDistinct(string S, string T)
    {
        int m = T.length();
        int n = S.length();
        
        // 构造矩阵(m+1)×(n+1)
        vector<vector<int> > array(m + 1, vector<int>(n + 1, 0));
        //初始化第一行
        for (int i = 0; i < n+1; i++)
            array[0][i] = 1;
        //初始化第一列
        for (int i = 1; i < m + 1; i++)
            array[i][0] = 0;
        
        // 遍历每一行
        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                if (T[i - 1] != S[j - 1])
                    array[i][j] = array[i][j - 1];
                else
                    array[i][j] = array[i][j - 1] + array[i - 1][j - 1];
            }
        }
        return array[m][n];
    }
};

但是上述代码的过程占用了很多无效空间。只通过一个一维数组就能够完成上述操作。

class Solution
{
public:
    int numDistinct(string S, string T)
    {
        int m = S.length();
        int n = T.length();
        
        vector<int> array(n + 1);
        array[0] = 1; // T为空时，满足条件的子序列为1
        
        for (int i = 0; i < m + 1; i++)
        {
            // 此处更改数组的数值时从后向前改，因为当前值与上次的结果密切相关
            for (int j = min(i , n); j > 0; j--) 
            {
                if (S[i - 1] == T[j - 1])
                    array[j] = array[j] + array[j - 1];
            }
        }
        return array[n];
    }
};

参考链接：https://www.nowcoder.com/questionTerminal/ed2923e49d3d495f8321aa46ade9f873?f=discussion