正则表达式匹配

题目描述

​ 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

递归

​ 如果是*的话，考虑将p串里这个*及前面的字母跳过去（匹配0个），或者在s串匹配一个里和*前面字母相同的字母（匹配1个）。就是暴力递归每次匹配0个或1个。

//递归
bool match(char* str, char* pattern)
{
    char *a=str;
    char *b=pattern;
    int lena=strlen(a);
    int lenb=strlen(b);
    if(lenb==0)return lena==0;
    bool flag=lena>0&&(b[0]=='.'||(a[0]==b[0]));
    if(lenb>1&&b[1]=='*'){
        return match(a,b+2)||(flag&&match(a+1,b));
    }else{
        return flag&&match(a+1,b+1);
    }
}

DP

class Solution {
public:
    bool isMatch(string s, string p) {
        s = " " + s;//防止该案例：""\n"c*"
        p = " " + p;
        //可以少一部分初始化
        int m = s.size(), n = p.size();
        bool dp[m + 1][n + 1];
        memset(dp, false, (m + 1) * (n + 1));
        dp[0][0] = true;//长度为0一定是匹配的
        for (int i = 1; i <= m; i++) {//枚举两个字符串的长度
            for (int j = 1; j <= n; j++) {//dp的意思是s长度为i,p长度为j是否匹配
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    //如果两个字符相等或者p是点就同时匹配两个
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    //如果是*
                    if (s[i - 1] != p[j - 2] && p[j - 2] != '.')
                        //二者不相等的时候，就将这个*和前面的字符都跳过去看是否匹配
                        dp[i][j] = dp[i][j - 2];
                    else {
                        //二者相等的时候,可以选择跳过或者选一个或多个
                        dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
                        // dp[i][j] = dp[i-1][j]  多个字符匹配的情况    
                        //or dp[i][j] = dp[i][j-1]  单个字符匹配的情况
                        //or dp[i][j] = dp[i][j-2]  没有匹配的情况    
                    }
                }
            }
        }
        return dp[m][n];
    }
};