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正则表达式匹配，题意理解要注意.*可以理解为任意字符串，例如：
代码语言：javascript复制isMatch("ab", ".*") → true“.”和普通字符的匹配非常容易，关键在于“*”，
由于不知道它可能代表多少个字符，而前面的决定会影响后面，所以自然而然想到DFS。
DFS暴搜的时候需要注意边界条件和终止搜索的条件，详见代码。
代码语言：javascript复制class Solution {
public:
bool isMatch(string s, string p) {
int len1=s.length(),len2=p.length();
if(len2==0)
return len1==0;
if(len2==1) //string 类型的最后一位为len-1，为了保证可以访问p[1],长度至少为2
return (len1==1) && (s[0]==p[0] || p[0]=='.');
if(p[1]=='*')
{
for(int i=0;i<len1 && (p[0]==s[i] || p[0]=='.');i )
if(isMatch(s.substr(i 1,len1-i-1),p.substr(2,len2-2)))
return true;
return isMatch(s,p.substr(2,len2-2));
}
else
{
if(len1==0)
return false;
else
return isMatch(s.substr(1,len1-1),p.substr(1,len2-1)) && ((s[0]==p[0]) || (p[0]=='.'));
}
}
};
