solution.md

# 正则表达式匹配

<p>给你一个字符串 <code>s</code> 和一个字符规律 <code>p</code>，请你来实现一个支持 <code>'.'</code> 和 <code>'*'</code> 的正则表达式匹配。</p><ul>	<li><code>'.'</code> 匹配任意单个字符</li>	<li><code>'*'</code> 匹配零个或多个前面的那一个元素</li></ul><p>所谓匹配，是要涵盖 <strong>整个 </strong>字符串 <code>s</code>的，而不是部分字符串。</p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>s = "aa" p = "a"<strong><br />输出：</strong>false<strong><br />解释：</strong>"a" 无法匹配 "aa" 整个字符串。</pre><p><strong>示例 2:</strong></p><pre><strong>输入：</strong>s = "aa" p = "a*"<strong><br />输出：</strong>true<strong><br />解释：</strong>因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>s = "ab" p = ".*"<strong><br />输出：</strong>true<strong><br />解释：</strong>".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>s = "aab" p = "c*a*b"<strong><br />输出：</strong>true<strong><br />解释：</strong>因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。</pre><p><strong>示例 5：</strong></p><pre><strong>输入：</strong>s = "mississippi" p = "mis*is*p*."<strong><br />输出：</strong>false</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= s.length <= 20</code></li>	<li><code>0 <= p.length <= 30</code></li>	<li><code>s</code> 可能为空，且只包含从 <code>a-z</code> 的小写字母。</li>	<li><code>p</code> 可能为空，且只包含从 <code>a-z</code> 的小写字母，以及字符 <code>.</code> 和 <code>*</code>。</li>	<li>保证每次出现字符 <code>*</code> 时，前面都匹配到有效的字符</li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    string s = "aa";
    string p = "a";
    cout << sol.isMatch(s, p) << endl;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    bool isMatch(string s, string p)
    {
        return match(s, p, s.length() - 1, p.length() - 1);
    }
    bool match(const string &s, const string &p, int rs, int rp)
    {
        if (rp == -1 && rs == -1)
        {
            return true;
        }
        if (rs < -1 || rp <= -1)
            return false;
        if (p[rp] == '.')
        {
            return match(s, p, rs - 1, rp - 1);
        }
        else if (p[rp] == '*')
        {
            if (p[rp - 1] != s[rs] && p[rp - 1] != '.')
            {
                return match(s, p, rs, rp - 2);
            }
            else
            {
                return match(s, p, rs, rp - 2);
            }
        }
        else
        {
            if (p[rp] != s[rs])
            {
                return false;
            }
            else
            {
                return match(s, p, rs - 1, rp - 1);
            }
        }
    }
};

```
## 选项


### A

```cpp
class Solution
{
public:
    bool isMatch(string s, string p)
    {
        int lens = s.length(), lenp = p.length();
        if (lenp == 0)
            return lens == 0;
        if (lenp == 1)
        {
            if (lens == 0)
                return false;
            if (lens != 0 && (p[0] == s[0] || p[0] == '.'))
                return isMatch(s.substr(1), p.substr(1));
            else
                return false;
        }
        if (lenp >= 2)
        {
            if (p[1] != '*')
            {
                if (s.length() != 0 && (p[0] == s[0] || p[0] == '.'))
                    return isMatch(s.substr(1), p.substr(1));
                else
                    return false;
            }
            else
            {
                while (s.length() != 0 && (p[0] == s[0] || p[0] == '.'))
                {
                    if (isMatch(s, p.substr(2)))
                        return true;
                    else
                    {
                        s = s.substr(1);
                    }
                }
                return isMatch(s, p.substr(2));
            }
        }
    }
};
```

### B

```cpp
class Solution
{
public:
    bool first_match(string s, string p, int i, int j)
    {
        return s[i] == p[j] || p[j] == '.';
    }

    bool isMatch(string s, string p)
    {
        vector<vector<bool> > dp(s.size() + 1, vector<bool>(p.size() + 1));
        dp[0][0] = true;

        for (int j = 2; j <= p.size(); j++)
        {
            dp[0][j] = p[j - 1] == '*' && dp[0][j - 2];
        }
        for (int i = 0; i < s.size(); i++)
        {
            for (int j = 0; j < p.size(); j++)
            {

                if (p[j] == '*')
                {
                    dp[i + 1][j + 1] = dp[i + 1][j - 1] || first_match(s, p, i, j - 1) && dp[i][j + 1];
                }
                else
                {
                    dp[i + 1][j + 1] = first_match(s, p, i, j) && dp[i][j];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};
```

### C

```cpp
class Solution
{
public:
    bool isMatch(string s, string p)
    {

        if (p.empty())
            return s.empty();
        bool first = !s.empty() && (p[0] == '.' || s[0] == p[0]);
        if (p[1] == '*')
            return first && isMatch(s.substr(1), p) || isMatch(s, p.substr(2));
        else
            return first && isMatch(s.substr(1), p.substr(1));
    }
};
```