# 正则表达式匹配
以下错误的选项是？
## 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));
    }
};
```