leetcode 正则表达式匹配

10. 正则表达式匹配

绞尽脑汁，想了两天才搞定

以确定性的字符串为分界，分而治之。
比如 p = "a*.*c*abcd*e*c*."; s = "ijpqabcxyz";，其中 abc 即为确定性字符串，找到目标字符串 s 中的 abc 出现的位置

也就是把 isMatch("ijpqabcxyz", "a*.*c*abcd*e*c*.") 转换成了 isMatch("ijpq", "a*.*c*") 和 isMatch("xyz", "d*e*c*.")

int find(char* s, int start_pos, int sn, char* p, int pn){
    for(int i=start_pos; i s: %s, sn: %d, p: %s, pn: %d\n", s, sn, p, pn);
    if(sn <= 0 && pn <= 0) return true;
    // if(sn <= 0 || pn <= 0) return false;

    int start = -1, stop = -1; // [start, stop)
    for(int i=0; i= pn) return false;
            }
        }else{
            // p[i] == 'c' // c stand for character
            // p[i+1] == '*'
            char c = p[i];
            // if(j==sn) return true;
            for(int k=j;k<=sn;k++){
                if(check(s+k, sn-k, p+i+2, pn-i-2)) return true;
                if(s[k] != c) return false;
            }
            return false;
        }
    }

    return false;
}

bool isMatch(char * s, char * p){
    return check(s, strlen(s), p, strlen(p));
}