leetcode 10 -- Regular Expression Matching

** 前言 **

初看到这道题，毫无思路，逃避好几天，看学长博客，才找到思路，即使这样，仍调试好大一会儿，刷题好痛苦。。。

** 题目 **

Implement regular expression matching with support for ‘.’ and ‘’.
‘.’ Matches any single character.
‘’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a”) → true
isMatch(“aa”, “.*”) → true
isMatch(“ab”, “.*”) → true
isMatch(“aab”, “ca*b”) → true

** 题意 **

完成类似正则表达式的匹配功能

** 思路 **

针对p[1]是否等于*来进行递归滑动

** 代码 **

bool isMatch(char *s,char *p)
{
    if(p[0]=='\0')
    {
        return s[0]=='\0';
    }
    if(s[0]=='\0')
    {
        if(p[1]=='*')
        {
            return isMatch(s,p+2);
        }
        return false;
    }
    if(p[1]=='*')
    {
        if(s[0]==p[0]||p[0]=='.')
        {
            if(strlen(p)>=4 && p[0]==p[2] && p[3]=='*')
                return isMatch(s,p+2);//此处总觉得是有些取巧，针对超时
            return isMatch(s+1,p)||isMatch(s+1,p+2)||isMatch(s,p+2);
        }
        else
        {
            return isMatch(s,p+2);
        }
    }
    else
    {
        if(s[0]==p[0]||p[0]=='.')
        {
            return isMatch(s+1,p+1);
        }
    }
    return false;
}