【动态规划算法练习】day13

摘星

发布于 2023-10-15 15:48:19

1410

发布于 2023-10-15 15:48:19

文章被收录于专栏：C/C++学习

一、115. 不同的子序列

1.题目简介

115. 不同的子序列给你两个字符串 s 和 t ，统计并返回在 s 的子序列中 t 出现的个数。题目数据保证答案符合 32 位带符号整数范围。

2.解题思路

3.代码

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<double> v(t.size() + 1, 0);
        vector<vector<double>> dp(s.size() + 1, v);
        //dp[i][j]表示有多少种可以以i-1为结尾的字符串s得到从以j-1为结尾的字符串t的方案。
        //初始化
        for(int i = 0;i < s.size(); ++i)//这是t为空的情况，空字符串也是子序列的一种
        {
            dp[i][0] = 1;
        }
        for(int i = 1;i <= s.size(); ++i)
        {
            for(int j = 1;j <= t.size(); ++j)
            {
                if(s[i - 1] == t[j - 1])
                {
                    dp[i][j] = (double)dp[i - 1][j - 1] + dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.size()][t.size()];
    }
};

4.运行结果

二、44. 通配符匹配

1.题目简介

44. 通配符匹配给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ’ * ’ 匹配规则的通配符匹配： ‘?’ 可以匹配任何单个字符。 ’ * ’ 可以匹配任意字符序列（包括空字符序列）。判定匹配成功的充要条件是：字符模式必须能够完全匹配输入字符串（而不是部分匹配）。

2.解题思路

3.代码

class Solution {
public:
    bool isMatch(string s, string p) {
        vector<bool> v(p.size() + 1, false);
        vector<vector<bool>> dp(s.size() + 1, v);
        //初始化
        dp[0][0] = true;//用空字符串匹配空字符串，匹配成功
        for(int j = 1;j <= p.size(); ++j)//初始化前导*
        {
            if(p[j - 1] == '*')
            {
                dp[0][j] = true;
            }
            else break;//两个*之间的元素是否匹配不确定
        }
        for(int i = 1;i <= s.size(); ++i)
        {
            for(int j = 1;j <= p.size(); ++j)
            {
                if(p[j - 1] != '*')
                {
                    dp[i][j] =  dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');//注意小括号
                }
                else
                {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];//前者是用*匹配i以及i之前的多个字符，后者是用*匹配了个空字符序列。
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

4.运行结果

三、10. 正则表达式匹配

1.题目简介

10. 正则表达式匹配给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ’ * ’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ’ * ’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

2.解题思路

3.代码

class Solution {
public:
    bool _isMatch(const string& s, const string& p, int sb, int pb)
    {
        if(sb == s.size() && pb == p.size()) return true;
        if(sb != s.size() && pb == p.size()) return false;
        if(p[pb + 1] != '*')
        {
            if(s[sb] == p[pb] || (sb != s.size() && p[pb] == '.'))
            {
                return _isMatch(s, p, sb + 1, pb + 1);
            }
            return false;
        }
        else
        {
            if(s[sb] == p[pb] || (sb != s.size() && p[pb] == '.'))
            {
                return _isMatch(s, p, sb + 1, pb) || _isMatch(s, p, sb, pb + 2);
            }
            return _isMatch(s, p, sb, pb + 2);
        }
    }
    bool isMatch(string s, string p) {
        return _isMatch(s, p, 0, 0);
    }
};