给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
假设s字符串为s0, s1, … sn-1; p字符串为p0, p1, … pn-1.
答案和p[j]是否为’*’有关：
- 1 当p[j] != ‘*’时
- 1.1 如果p[j]为字母，则判断s[i]和s[j]是否匹配
- 1.2 如果p[j]为’.’，则dp[i][j] = dp[i-1][j-1]
- 2 如果p[j] == ‘*’时
- 2.1 如果N==0，则p字符串中字母+’*’则去除，则dp[i][j] = dp[i][j-2]
- 2.2 如果N>=1，则p字符串中字母+’*’一直保留，对字符串s进行匹配，则判断s[i]是否等于p[j-1] || p[j-1]是否等于’.’。
代码详解：
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s;
p = ' ' + p;
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
dp[0][0] = true;
for(int i=0; i<=n; i++){
for(int j=1; j<=m; j++){
if (p[j] != '*')
dp[i][j] = i && j && (s[j] == p[j] || p[j] == '.') && dp[i-1][j-1];
else
dp[i][j] = (j>=2 && dp[i][j-2]) || (i && j && (s[i]== p[j-1] || p[j-1] == '.') && dp[i-1][j]);
}
}
return dp[n][m];
}
};