Regular Expression Matching
Implement regular expression matching withsupport for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the precedingelement.
The matching should cover the entireinput 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
这题很多corner case需要考虑，也是看了leetcode开发者的这篇文章（http://articles.leetcode.com/2011/09/regular-expression-matching.html）恍然大悟的，由于'.'和'*'的特殊性，用贪心会有bug，文章里面详细描述了几个case。作者指出了两点：
1. If the next character of pis NOT '*',then it must match the current charactor of s. Continue patternmatching with the next charactor of both s and p.
2.If the next character of p is '*',then we do a brute forceexhuastive matching of 0,1,or more repeats current charactor of p... Until weCould not match any more charactors.
C++代码如下（由于Python字符串的特性就懒得给python代码了）
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);
}
}
};