Regular Expression Matching
Desicription
Implement regular expression matching with support for '.'
and '*'
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| '.' 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
|
Solution
1 2 3 4 5 6 7 8 9 10 11
| class Solution { public: bool isMatch(string s, string p) { if(p.empty()) return s.empty(); if(p[1] == '*') return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p)); else return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1)); } };
|