Leetcodes Solutions 10 Regular Expression Matching

zhuanlan.zhihu.com

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

Notice the diffrence from wildcard matching

? Matches any single character.

* Matches any sequence of characters (including the empty sequence).

思路1

class Solution {private: bool helper(const string &s, const string &p, int sS, int pS) { int sSize = s.size(), pSize = p.size(), i, j; if(pS==pSize) return sS ==sSize; // if p goes to its end, then only if s also goes to its end to return true; //divide cases into two groups(if the next p char is * or not) if(p[pS+1]!=*) { if( sS<sSize && (p[pS]==s[sS] || p[pS] == .)) return helper(s, p, sS+1, pS+1); } else { if(helper(s, p, sS,pS+2)) return true; while(sS<sSize && (p[pS]==s[sS] || p[pS] == .)) if(helper(s,p, ++sS, pS+2)) return true; } return false; }public: bool isMatch(string s, string p) { helper(s, p, 0, 0); }};

推薦閱讀：