代码随想录训练营Day54：Leetcode392、115

Leetcode392：

问题描述：

给定字符串 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;
           }
};

Leetcode115：

问题描述：

给你两个字符串 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];
    }
};

原文地址：https://blog.csdn.net/maybeyaluokenai/article/details/139283766

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！