leetcode10.正则表达式匹配

逃离我推掉我的手 2023-06-03 14:53 113阅读 0赞

1.递归

\- 若p为空，且s也为空，返回true，反之返回false

\- 若p的长度为1，且s长度也为1，且相同或是p为'.'则返回true，反之返回false

\- 若p的第二个字符不为\*，且此时s为空则返回false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配

\- 若p的第二个字符为\*，s不为空且字符匹配，调用递归函数匹配s和去掉前两个字符的p，若匹配返回true，否则s去掉首字母

\- 返回调用递归函数匹配s和去掉前两个字符的p的结果

bool isMatch(string s, string p)
    {
        //实现 p 能够匹配 s
        // .任意字符 * 任意个数
        //递归
        if(p.empty())
            return s.empty();
        auto first_match = !s.empty() && (s[0] == p[0] || p[0] == '.');
        if(p.length() >= 2 && p[1] == '*')
            return isMatch(s,p.substr(2)) || (first_match && isMatch(s.substr(1),p));
        else
            return first_match && isMatch(s.substr(1), p.substr(1));
    }

2.动态规划

dp\[i\]\[j\]表示s\[0,i)和p\[0,j)是否match

*1. P\[i\]\[j\] = P\[i - 1\]\[j - 1\], if p\[j - 1\] != '\*' && (s\[i - 1\] == p\[j - 1\] || p\[j - 1\] == '.');  
2. P\[i\]\[j\] = P\[i\]\[j - 2\], if p\[j - 1\] == '\*' and the pattern repeats for 0 times;  
3. P\[i\]\[j\] = P\[i - 1\]\[j\] && (s\[i - 1\] == p\[j - 2\] || p\[j - 2\] == '.'), if p\[j - 1\] == '\*' and the pattern repeats for at least 1 times.*

bool isMatch2(string s, string p)
    {
        //动态规划
        
        vector<vector<bool>> dp(s.length()+1, vector<bool>(p.length()+1, false));
        dp[0][0] = true;
        for(int i = 0;i<=s.length();i++)
        {
            for(int j = 1;j<=p.length();j++)
            {
                if(j>1 && p[j-1] == '*')
                    dp[i][j] = dp[i][j-2] ||
                            (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                else
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] &&
                            (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
        return dp[s.length()][p.length()];
    }

转载于:https://www.cnblogs.com/didiaoxiaoguai/p/10892185.html