LeetCode 115. Distinct Subsequences

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 115. Distinct Subsequences 原题链接困难

作者：

yxc , 2018-05-18 16:00:45 , 所有人可见 , 阅读 3352

10

6

题目描述

给定字符串 $S$ 和 $T$，统计 $S$ 中有多少个不同的子序列和 $T$ 相等。

字符串的子序列是指：将原字符串删掉若干字符后，其余字符相对顺序不改变，所得到的新串（例如："ACE"是"ABCDE"的子序列，而"AEC"不是）。

样例1

输入：S = "rabbbit", T = "rabbit"
输出：3
解释：如下所示，共有3种方案。
'^' 表示选择的字符

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

样例2

输入：S = "babgbag", T = "bag"
输出：5
解释：如下所示，共有5种方案。
'^' 表示选择的字符

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

算法

(动态规划) $O(nm)$

可以换一种考虑问题的方式：用 $S$ 中的字符，按顺序匹配 $T$ 中的字符，问有多少种方式可以匹配完 $T$ 中的所有字符。

可以用动态规划来做：
$f[i][j]$ 表示用 $S$ 的前 $i$ 个字符，能匹配完 $T$ 的前 $j$ 个字符的方案数。
初始化：因为 $S$ 可以从任意一个字符开始匹配，所以 $f[i][0] = 1, \forall i \in [0, len(S)]$。
状态转移：

如果 $S[i - 1] \neq T[j - 1]$，则 $S[i-1]$ 不能匹配 $T[j-1]$，所以 $f[i][j] = f[i - 1][j]$；
如果 $S[i - 1] = T[j - 1]$，则 $S[i-1]$ 既可以匹配 $T[j-1]$，也可以不匹配 $T[j - 1]$，所以 $f[i][j] = f[i - 1][j] + f[i - 1][j - 1]$；

时间复杂度分析：假设 $S$ 的长度是 $n$，$T$ 的长度是 $m$，则共有 $nm$ 个状态，状态转移的复杂度是 $O(1)$，所以总时间复杂度是 $O(nm)$。

C++ 代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<long long>> f(n + 1, vector<long long>(m + 1));

        for (int i = 0; i <= n; i ++ ) f[i][0] = 1;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (s[i - 1] == t[j - 1])
                    f[i][j] += f[i - 1][j - 1];
            }

        return f[n][m];
    }
};

18 评论

Biang 4个月前

2024年7月23日题目已经改为对 1e9+7取模了

class Solution {
public:
    const int MOD=1e9+7;
    vector<int> pos[26];
    int numDistinct(string s, string t) {
        /*
            f(i,j) 表示t中前i个字符在s的前j个字符中出现的次数
            f(i,j)
                对于字符sj应该分为两种情况
                1. 不用sj f(i,j)=f(i,j-1);
                2. 用上sj 当ti==sj f(i,j)+=f(i-1,j-1);
        */
        s=" "+s;
        t=" "+t;

        int n=t.size();
        int m=s.size();
        int f[1005][1005];
        memset(f,0,sizeof f);
        for(int i=0;i<m; i++) f[0][i]=1;

        for(int i=1; i<n; i++){
            for(int j=1; j<m; j++){
                f[i][j]=f[i][j-1];
                if(t[i]==s[j]) f[i][j]=(f[i][j]+f[i-1][j-1])%MOD;
            }
        }
        return f[n-1][m-1];
    }

};

PYF 2023-09-30 17:40

使用unsigned自动取模

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<unsigned>> f(n + 1, vector<unsigned>(m + 1, 0));
        for (int i = 0; i <= n; i ++) f[i][0] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
            {
                f[i][j] = f[i - 1][j];
                if (s[i - 1] == t[j - 1]) f[i][j] += f[i - 1][j - 1];
            }
        return f[n][m];
    }
};