哪个平台做网站比较好,网站建设产品,大型企业网站建设方案,dedecms网站版权信息给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 10^9 7 取模
示例 1#xff1a;
输入#xff1a;s rabbbit, t rabbit
输出#xff1a;3
解释#xff1a;如下所示, 有 3 种可以从 s 中得…给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 10^9 7 取模
示例 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
思路和分析
下文参考((OO))ブ笨猪爆破组的文章解法和文字115. 不同的子序列 - 力扣LeetCode
在s串身上“挑选”字符去匹配 t串 的字符求挑选的方式数
1递归思路抓住“选”s 要按照 t 来挑选逐字符考察“选”或“不选”分别来到什么状态
1.s[i] t[j] 举例s 为 babgbag,t 为 bag末尾字符相同故 s 有两种选择注意int n s.length(),m t.length(); 1.用s[n-1] 去匹配掉 t[m-1]问题规模缩小继续考察 babgba 和 ba 2.若s[n-1] 不去匹配掉 t[m-1]可由于t[m-1] 仍需被匹配于是在 babgba 中继续挑考察babgba 和 bag是否用s[n-1]去匹配t[m-1]是两种不同的挑选方式各自做下去所产生的方式数相加起来是大问题的解
2.s[i] ! t[j] s[i] 不匹配 t[j]唯有拿 s[i] 之前的子串去匹配
2递归函数返回
返回 从开头到s[i]的子串中出现『从开头到t[j]的子串』的次数。 即从 前者 选字符去匹配 后者 的方案数
3递归树底部的base case
一步步地递归压栈子问题规模子串长度在变小
小到 t 变成空串此时 s 去匹配它方式只有一种就是什么字符都不用挑或 s 也是空串啥也不用做也可匹配方式数也是1小到 s 变成空串但t不是 s 是没有办法匹配 t 的方式数为0
递归函数的参数可以传子串或索引这里推荐用索引描述子问题因为不用每次都切割字符串也更容易迁移到dp解法去
一、递归搜索 (会超时)
超出时间限制 class Solution {
public:// 递归搜索 (会超时)int numDistinct(string s,string t) {const int n s.length(),m t.length();functionint(int,int) dfs [](int i,int j) - int {if(j0) return 1;// base caseif(i0) return 0;// 这两个base case 的顺序不能调换因为 i0 且 j0 时 应该返回1if(s[i] t[j]) return dfs(i-1,j) dfs(i-1,j-1);else return dfs(i-1,j);};return dfs(n-1,m-1);}
}; 二、递归搜索 保存计算结果 记忆化搜索
二维memo数组 存储计算过的子问题的结果 // 递归搜索 保存计算结果 记忆化搜索int numDistinct(string s, string t) {int n s.length(),m t.length(),memo[n][m]; // 二维memo数组 存储计算过的子问题的结果memset(memo,-1,sizeof(memo));// -1 表示没有访问过functionint(int,int) dfs [](int i,int j) - int { // 从开头到s[i]的子串中出现『从开头到t[j]的子串』的 次数if(j0) // base case 当j指针越界此时t为空串s不管是不是空串匹配方式数都是1return 1;if(i0) // base case i指针越界此时s为空串t不是s怎么也匹配不了t方式数0return 0;if (memo[i][j] ! -1) // memo中有当前遇到的子问题的解直接拿来返回return memo[i][j];if (s[i] t[j]) { // t[j]被匹配掉对应dfs(i-1, j-1)不被匹配掉对应dfs(i-1, j)memo[i][j] dfs(i-1, j) dfs(i-1, j-1);} else {memo[i][j] dfs(i-1, j);}return memo[i][j];// 返回当前递归子问题的解};return dfs(n-1,m-1);//从开头到s[n-1]的子串中出现『从开头到t[m-1]的子串』的次数} 也可以写成这样的代码 class Solution {
public: // 递归搜索 保存计算结果 记忆化搜索int numDistinct(string s, string t) {int n s.length(),m t.length(),memo[n][m]; memset(memo,-1,sizeof(memo));functionint(int,int) dfs [](int i,int j) - int { if(j0) return 1;if(i0) return 0;int res memo[i][j];if (res ! -1) return res;if (s[i] t[j]) return res dfs(i-1, j) dfs(i-1, j-1);return res dfs(i-1, j);};return dfs(n-1,m-1);}
}; 三、动态规划 与 递归 的区别
递归公式 if (s[i] t[j]) { memo[i][j] dfs(i-1, j) dfs(i-1, j-1);
} else {memo[i][j] dfs(i-1, j);
} 递归是自上而下调用子问题自下而上被解决最后解决了整个问题而dp是从base case 出发通过在dp数组记录中间结果自下而上地顺序地解决子问题
dp解法
1.确定dp数组dp table以及下标的含义
dp[i][j]:从开头到s[i-1]的子串中出现『从开头到t[j-1]的子串』的 次数。即
前 i 个字符的 s 子串中出现前 j 个字符的 t 子串的次数或者说 以i-1为结尾的s子序列中出现以j-1为结尾的 t 的个数
2.确定递推公式
状态转移方程
当s[i-1] ! t[j-1]时有dp[i][j] dp[i-1][j]当s[i-1] t[j-1]时有dp[i][j] dp[i][j] dp[i-1][j-1] dp[i-1][j]
3.dp数组初始化
base case
j0时dp[i][0] 1i0时dp[0][j] 0 也可从递推公式dp[i][j] dp[i-1][j-1] dp[i-1][j];和dp[i][j] dp[i-1][j];中可以看出dp[i][j]是从上方和左方推导而来的故dp[i][0] 和 dp[0][j] 是一定要初始化的
4.确定遍历顺序
从递推公式我们可以看出dp[i][j]是从上方和左方推导而来的所以遍历的时候一定是从上到下、从左到右可以保证dp[i][j]可以根据之前计算出来的数值进行计算
5.举例推导dp数组
以sheeehehedatheheda为例推导dp数组状态如下可以参考此图在不知道递推式的情况下找出规律手推递推式 以sbabgbagtbag为例推导dp数组状态如下 以srabbbittrabbit为例推导dp数组状态如下 一动态规划 二维dp class Solution {
public:// 动态规划 二维dp数组int numDistinct(string s, string t) {int n s.length(),m t.length();uint64_t dp[n1][m1];memset(dp,0,sizeof(dp));for(int i0;in;i) dp[i][0] 1;// for(int j1;jm;j) dp[0][j] 0;for(int i1;in;i) {for(int j1;jm;j) {if(s[i-1] t[j-1]) dp[i][j] dp[i-1][j-1] dp[i-1][j];else dp[i][j] dp[i-1][j];}}return dp[n][m];}
};
时间复杂度: O(n * m)空间复杂度: O(n * m) 二动态规划 二维dp 优化空间复杂度
class Solution {
public:// 动态规划 二维dp优化空间复杂度int numDistinct(string s, string t) {int n s.length(),m t.length();uint64_t dp[2][m1];memset(dp,0,sizeof(dp));for(int i0;i2;i) dp[i][0] 1;for(int j1;jm;j) dp[0][j] 0;for(int i1;in;i) {for(int j1;jm;j) {if(s[i-1] t[j-1]) dp[i%2][j] dp[(i-1)%2][j-1] dp[(i-1)%2][j];else dp[i%2][j] dp[(i-1)%2][j];}}return dp[n%2][m];}
}
时间复杂度: O(n * m)空间复杂度: O(m) 三动态规划 一维dp滚动数组 优化空间复杂度
class Solution {
public:// 动态规划 一维dp 优化空间复杂度int numDistinct(string s, string t) {int n s.length(),m t.length();uint64_t dp[m1];memset(dp,0,sizeof(dp));dp[0] 1;for(int j1;jm;j) dp[j] 0;for(int i1;in;i) {// int pre dp[0];// for(int j1;jm;j) {// int tmp dp[j];// if(s[i-1] t[j-1]) dp[j] pre dp[j];// else dp[j] dp[j];// pre tmp;// }for(int jm;j1;j--) {if(s[i-1] t[j-1]) dp[j] dp[j-1] dp[j];}}return dp[m];}
};
时间复杂度: O(n * m)空间复杂度: O(m) 参考和推荐文章、视频
115. 不同的子序列 - 力扣LeetCode
代码随想录 (programmercarl.com)
动态规划之子序列为了编辑距离做铺垫 | LeetCode115.不同的子序列_哔哩哔哩_bilibili
