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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("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);}};
版权声明:本文为博主原创文章,未经博主允许不得转载。
没有什么可凭仗,只有他的好身体,没有地方可去,只想到处流浪。