题目:
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
正则表达式匹配,. 可以匹配任何单个字符。 * 零次或多次匹配前面的字符或子表达式。例如,zo* 可以匹配“z”和“zoo”。前面一个*表示o一次也没有。
思路:
当前字符的下一个字符为 * 时,有两种情况,1、* 表示0次前一个字符,则对(s,p+2)递归调用匹配。如 s = abc,p = m*abc 。
2、如果当前字符匹配,则对(s+1,p)递归调用匹配。此时 * 至少表示一次前一个字符。如 s = aaabc,p = a*abc 。
两种情况只要有一个满足即匹配。
代码:
class Solution { public: bool isMatch(const char *s,const char *p) { if (*p == '\0') return *s == '\0'; // next char is not '*',then must match current character if (*(p + 1) != '*') { if (*p == *s || (*p == '.' && *s != '\0')) return isMatch(s + 1,p + 1); else return false; } else { // next char is '*' return isMatch(s,p + 2) || (*p == *s || (*p == '.' && *s != '\0')) && isMatch(s + 1,p); } } };
更新:
class Solution { public: bool isMatch(string s,string p) { const char *s1 = s.c_str(); const char *s2 = p.c_str(); return isMatch(s1,s2); } bool isMatch(const char *s1,const char *p1) { if(*p1 == '\0') return *s1 == '\0'; if(*(p1+1) != '*') { if(*s1 == *p1 || (*p1 == '.' && *s1 != '\0')) return isMatch(s1+1,p1+1); else return false; } else { return isMatch(s1,p1+2) || (*s1 == *p1 || (*p1 == '.' && *s1 != '\0')) && isMatch(s1+1,p1); } } };