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]; } };