请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。
样例
输入：
s="aa"
p="a*"
输出:true
分析：
状态表示：f[i][j]表示p从j开始到结尾，是否能匹配s从i开始到结尾
状态转移：
如果p[j+1]不是通配符''，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
如果p[j+1]是通配符''，则下面的情况只要有一种满足，f[i][j]就是真；
f[i][j+2]是真；
s[i]可以和p[j]匹配，且f[i+1][j]是真；
第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？
最直观的转移方式是这样的：枚举通配符'*'可以匹配多少个p[j]，只要有一种情况可以匹配，则f[i][j]就是真；
这样做的话，我们发现，f[i][j]除了枚举0个p[j]之外，其余的枚举操作都包含在f[i+1][j]中了，所以我们只需判断
f[i+1][j]是否为真，以及s[i]是否可以和p[j]匹配即可。
时间复杂度分析：n
表示s的长度，m 表示p的长度，总共 nm 个状态，状态转移复杂度 O(1)，所以总时间复杂度是 O(nm).
/*
状态表示：f[i][j] 表示s[i,...] 和p[j,...] 相匹配
状态转移：
1.p[j]是正常字符即s[i] == p[j]，f[i][j] = f[i+1][j+1];
2.p[j]='.',f[i][j] = f[i+1][j+1];
3.p[j+1]='*'
3.1 匹配0次,f[i][j] = f[i][j+2]
3.2 匹配1次,f[i][j] = f[i+1][j]
3.3 匹配1次也包含在匹配多次里面了
边界情况：
f[n][m] = true;
*/
class Solution {
public:
int n, m;
//定义二维状态数组
vector<vector<int>> f;
bool isMatch(string s, string p) {
n = s.size(), m = p.size();
f = vector<vector<int>>(n+1, vector<int>(m+1,-1));
return dp(0, 0, s, p);
}
bool dp(int x, int y, string& s, string& p) {
//算过直接返回
if (f[x][y] != -1) return f[x][y];
//x,y分别等于最后一个元素时
if (y==m) return f[x][y] = x==n;
bool first_match = x < n && (p[y] == '.' || s[x] == p[y]);
if (y+1<m && p[y+1] == '*') {
//3.p[j+1]='*'
// 3.1 匹配0次,f[i][j] = f[i][j+2]
// 3.2 匹配1次,f[i][j] = f[i+1][j] && first_match
// 3.3 匹配1次也包含在匹配多次里面了
f[x][y] =dp(x, y+2, s, p) || first_match && dp(x+1, y, s, p);
} else {
//1.p[j]是正常字符即s[i] == p[j]，f[i][j] = f[i+1][j+1];
//2.p[j]='.',f[i][j] = f[i+1][j+1];
//这两种情况可以合为1种
f[x][y] = first_match && dp(x+1, y+1, s, p);
}
return f[x][y];
}
};
参考链接：AcWing
