@H_404_2@

Regular Expression Matching@H_404_2@
@H_404_2@

@H_404_2@

Implement regular expression matching withsupport for '.' and '*'.@H_404_2@

'.' Matches any single character.@H_404_2@

'*' Matches zero or more of the precedingelement.@H_404_2@

@H_404_2@

The matching should cover the entireinput string (not partial).@H_404_2@

@H_404_2@

The function prototype should be:@H_404_2@

bool isMatch(const char *s,const char *p)@H_404_2@

@H_404_2@

Some examples:@H_404_2@

isMatch("aa","a") →false@H_404_2@

isMatch("aa","aa") →true@H_404_2@

isMatch("aaa","aa") →false@H_404_2@

isMatch("aa","a*") →true@H_404_2@

isMatch("aa",".*") →true@H_404_2@

isMatch("ab",".*") →true@H_404_2@

isMatch("aab","c*a*b")→ true@H_404_2@

@H_404_2@

这题很多corner case需要考虑，也是看了leetcode开发者的这篇文章（http://articles.leetcode.com/2011/09/regular-expression-matching.html@H_301_95@）恍然大悟的，由于'.'和'*'的特殊性，用贪心会有bug，文章里面详细描述了几个case。作者指出了两点：@H_404_2@

class Solution {
public:
    bool isMatch(string s,string p) {
        return _is_match(s.c_str(),p.c_str());
    }
    
private:
    bool _is_match(const char* s,const char* p) {
        if (*p == '\0') {
            return *s == '\0';
        } 
        
        if (*(p + 1) != '*') {
            return ((*s == *p) || (*s != '\0' && *p == '.')) && _is_match(s + 1,p + 1);
        } else {
            while ((*s == *p) || (*s != '\0' && *p == '.')) {
                if (_is_match(s,p + 2)) {
                    return true;
                } 
                ++s;
            }
            return _is_match(s,p + 2);
        }
    }
};