[好题!] 剑指offer 19 正则表达式

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

我的方法没啥特殊的, 关键是想的足够周到
当遇到*的时候有三种可能: 下一个字符; 字符串不动且跳过这条规则; 字符和*不匹配

另外就是查缺补漏知识点, 空双引号也有一个结尾的'\0'

bool isMatch(char* s, char* p){
    //字符串是空,只有正则也是空或只接x*的时候匹配
    bool result = true;


    if((*s == 0) && (*p == 0))
        return true;
    else if((*s == 0) && (*(p+1)=='*'))
        return isMatch(s,p+2);
    else if(*s == 0)
        return false;
    //正则是空, 但是字符串不空, 不匹配
    else if(*p == 0)
        return false;


    //两个都不是空
    if(*s == *p)
    {
        if(*(p+1) == '*')
            result &= isMatch(s+1, p)|isMatch(s,p+2);//下一个字符;本字符跳过规则
        else 
            result &= isMatch(s+1, p+1);
    }
        
    else if(*p == '.')
    {
        if(*(p+1) == '*')
            result &= isMatch(s+1, p)|isMatch(s,p+2);
        else 
            result &= isMatch(s+1, p+1);
    }
    
    else //不匹配
    {
         if(*(p+1) == '*')
            result &= isMatch(s, p+2);
        else 
            result = false;
    }
    
    return result;
}

另一个思路更重要: 动态规划

设立[m][n]大小的数组, 利用i-1 j-1时候是否已经匹配的信息, 来推断这次是否匹配

注意循环中随时存在的i-1下标, 因此要随时判断下标是否合法

bool isMatch(char* s, char* p){
    int slen = strlen(s);
    int plen = strlen(p);

    //在table中, 用[0][0]存储空串, 用[i+1][j+1]存储第[i][j]是否匹配
    int **table = (int**) calloc(slen+1, sizeof(int*));
    for(int i = 0; i<=slen; i++)
        table[i] = (int*)calloc(plen+1, sizeof(int));


    for(int i = 0; i<=slen; i++)
    for(int j = 0; j<=plen; j++)
        {
            if(j == 0)//若正则为空, 只有字符串也是空的时候才匹配
            {
                table[i][j] = (i == 0);
            }
            else{
                if(p[j-1] != '*')//注意p[j-1]和table下标的对应关系
                {
                    if(i > 0)
                    if((p[j-1] == s[i-1]) || p[j-1] == '.')
                        table[i][j] |= table[i-1][j-1];
                }
                else 
                {
                    //不使用这个匹配,跳过
                    table[i][j] |= table[i][j-2];

                    //使用这个匹配,至少一次
                    if(i>0)
                    if((p[j-2] == s[i-1]) || p[j-2] == '.')
                        table[i][j] |= table[i-1][j];
                }
        }}
    return table[slen][plen];
}