1. 题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
2. 特殊说明
(1)这题和hdu6170题目一样。但是不同的是，对于下面这种情况：
ab .*
hdu6170判断为false，牛客网判断为true。实际上，在正则表达式里面，这个匹配结果也是true。
3. 解体思路
不妨令第一个串名字为$a$，长度为$n$；第二个串名字为$b$，长度为$m$。不难想到用$dp[i][j]$表示字符串$a$的前$i$个字符(这是口语化表达，前一个就是$a[0]$和$b[0]$)已经匹配，然后再转移到其他情况。显然，$dp[0][0]=true$，我们要的答案为$dp[n][m]$。
我们枚举串$a$和$b$的所有字符，设当前考虑的是$a$的第$i$个字符($a[i-1]$)和$b$的第$j$个字符($b[j-1]$)的匹配情况，那么，对于$b[j-1]$而言，有如下几种情况：
(1)$b[j-1]=='*'$：这时，又有如下几种情况：
①$b[j-2]$和$b[j-1]$合起来匹配$a$串的$0$个字符：转移式子为：$$dp[i][j]=dp[i][j-2]$$
②$b[j-2]$和$b[j-1]$合起来匹配$a$串的$1$个字符：转移式子为：$$dp[i][j]=dp[i-1][j-2]\&\&a[i-1]==b[j-2]$$
③$b[j-2]$和$b[j-1]$合起来匹配$a$串的$2$个字符以上：转移式子为：$$dp[i][j]=dp[i-1][j]\&\&a[i-2]==a[i-1]\&\&a[i-1]==b[j-2]$$
④考虑上面说明的特殊情况，如果$b[j-2]=='.'$，这时的$.*$组合也会出现上面三种情况，第一种情况和①一样，后面两种情况转移式子为：$$dp[i][j]=dp[i-1][j-1]|dp[i-1][j]$$
(2)$b[j-1]=='.'$：这时，转移式子为：$$dp[i][j]=dp[i-1][j-1]$$
(3)$b[j-1]$为普通字母：这时，转移式子为：$$dp[i][j]=dp[i-1][j-1]\&\&a[i-1]==b[j-1]$$
然后，注意边界控制，只要保证数组下标不会越界(负越界和正越界)即可。
4. 参考代码
class Solution {
public:
int n,m;
][];
bool match(char* str, char* pattern){
char *a=str,*b=pattern;
n=strlen(a);
m=strlen(b);
&&m==)return false;
;i<=n;++i)fill(dp[i],dp[i]+m+,false);
dp[][]=true;
;i<=n;++i){
;j<=m;++j){
]=='*'){
)dp[i][j]|=dp[i][j-];//对应情况(1).①和(1).④
&&j>=)dp[i][j]|=dp[i-][j-]&&a[i-]==b[j-];//对应情况(1).②
&&j>=)dp[i][j]|=dp[i-][j]&&a[i-]==a[i-]&&a[i-]==b[j-];//对应情况(1).③
&&b[j-]==][j-]|dp[i-][j];//对应情况(1).④
}
&&b[j-]==][j-];//对应情况(2)
)dp[i][j]|=dp[i-][j-]&&(a[i-]==b[j-]||b[j-]=='.');//对应情况(3)
}
}
return dp[n][m];
}
};