24
06/2015
[LeetCode] Regular Expression Matching
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解题思路：
题意为实现正则表达式的匹配。其中支持.和*
分成三种情况。设当前字符串和模式的下标分别为i，j
1、若当前模式匹配完毕，即p[j]=='\0'，若字符串结束，则返回true，否则返回false
2、若模式的下一个字符不是*，即p[j+1]!='*'。这里分情况讨论。
(1) 若s[i]==p[j]，递归验证i+1, j+1
(2) 若p[i]=='.'且s[i]!='\0'，递归验证i+1, j+1
(3) 否则，返回false
3、若模式的下一个字符是*，即p[j+1]=='*'，则不断通过递归回溯i+k，j+2（k从0增长至len(s)-i，j+2意味着越过当前字符和*）。
代码如下：
class Solution {
public:
bool isMatch(string s, string p) {
return matchHelper(s, p, 0, 0);
}
bool matchHelper(string& s, string& p, int i, int j){
if(p[j]=='\0'){
return s[i]=='\0';
}
if( p[j + 1] != '*'){
return ((s[i] == p[j]) || (p[j] == '.' && s[i]!='\0')) && matchHelper(s, p, i + 1, j + 1);
}
while((s[i] == p[j]) || (p[j] == '.' && s[i]!='\0')){
if(matchHelper(s, p, i, j+2)) return true;
i++;
}
return matchHelper(s, p, i, j+2);
}
};
0 条评论