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”, “c
a*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;
}