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