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); } };