最好设计网站建设,wordpress qq头像,网站栏目的分类,大型网站平台建设给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 10^9 7 取模。
示例 1#xff1a; 输入#xff1a;s “rabbbit”, t “rabbit” 输出#xff1a;3 解释#xff1a; 如下所示, 有 3 种可以从 s 中得到 “rabbit”…给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 10^9 7 取模。
示例 1 输入s “rabbbit”, t “rabbit” 输出3 解释 如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
示例 2 输入s “babgbag”, t “bag” 输出5 解释 如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
提示 1 s.length, t.length 1000 s 和 t 由英文字母组成
动态规划
class Solution {
public:int numDistinct(string s, string t) {int MOD 1e9 7;int m s.size(), n t.size();if(n m){return 0;}vectorvectorint f(m1, vectorint(n1));for(int i 0; i m; i){f[i][0] 1;}for(int i 1; i m; i){for(int j 1; j min(i, n) ; j){if(s[i-1] t[j-1]){f[i][j] (f[i-1][j-1] f[i-1][j]) % MOD;}else{f[i][j] f[i-1][j] % MOD;}}}return f[m][n];}
};时间复杂度O(mn)其中 m 和 n 分别是字符串 s 和 t 的长度。二维数组 dp 有 m1 行和 n1 列需要对 dp 中的每个元素进行计算。
空间复杂度O(mn)其中 m 和 n 分别是字符串 s 和 t 的长度。创建了 m1 行 n1 列的二维数组 dp。
这个题运用了动态规划的思想我们首先定义一个二维动态数组f[i][j]设 f[i][j] 表示字符串 s 的前 i 个字符中子序列中 t 的前 j 个字符出现的次数。
如果 s[i - 1] t[j - 1]那么 f[i][j] 既可以选择使用 s[i - 1] 来匹配 t[j - 1]也可以不使用 s[i - 1]。此时状态转移方程为
f[i][j] (f[i-1][j-1] f[i-1][j]) % MOD;如果 s[i - 1] ! t[j - 1]则无法匹配 t[j - 1]因此只能继承之前的状态
f[i][j] f[i - 1][j]最后返回f[m][n]。 优化滚动数组
class Solution {
public:int numDistinct(string s, string t) {int MOD 1e9 7;int m s.size(), n t.size();if(n m){return 0;}vectorint f(n1);f[0] 1;for(int i 1; i m; i){for(int j min(i, n); j 1 ; j--){if(s[i-1] t[j-1]){f[j] (f[j-1] f[j]) % MOD;}}}return f[n];}
};我们可以观察到f[i][j] (f[i-1][j-1] f[i-1][j]) % MOD;中f[I][j]上一行的前一个字符转换而来还有由同一行的前一个字符转换而来。所以我们可以省去行的空间只定义一个包含列的一维数组f[n]我们在循环中让j倒序我们就有f[j-1]等同于f[i-1][j-1]f[j]等同于f[i-1][j]。并且在f[i][j] f[i-1][j] % MOD;中f[i-1][j]会转换成f[j] f[j]所以我们不需要列出这种情况。
