赞
踩
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
- class Solution {
- public:
- //dp[i][j]代表s的前i个字符与t的前j个字符已经匹配字符的个数
- int dp[105][10005];
- bool isSubsequence(string s, string t) {
- int n1=s.size();
- int n2=t.size();
-
- for(int i=1;i<=n1;i++){
- for(int j=1;j<=n2;j++){
- if(s[i-1]==t[j-1])dp[i][j]=1+dp[i-1][j-1];
- else dp[i][j]=dp[i][j-1];
- }
- }
- return dp[n1][n2]==n1;
- }
- };
给你两个字符串 s
和 t
,统计并返回在 s
的 子序列 中 t
出现的个数,结果需要对 109 + 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
- class Solution {
- public:
- //dp[i][j]表示,s前i个字符与t前j个字符已经匹配的子序列个数
- long long dp[1005][1005];
- int numDistinct(string s, string t) {
-
- int n=s.size();
- int m=t.size();
- if(n<m)return 0;
- for(int i=0;i<=n;i++){
- dp[i][0]=1;
- }
-
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- if(s[i-1]==t[j-1]){
- dp[i][j]= (dp[i-1][j-1]+dp[i-1][j])%(long long)(1e9+7);
- }
- else
- dp[i][j]=dp[i-1][j]%(long long)(1e9+7);
- }
- }
- return dp[n][m];
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。