牛客网剑指Offer——正则表达式匹配

时间:2022-06-24 00:09:55

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