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
思路是分别处理a*、.*、.、a的情况。
三周前写的lengthy code如下:
1 class Solution { 2 public: 3 bool isMatch(const char *s, const char *p) { 4 int sn = strlen(s); 5 int pn = strlen(p); 6 return recursive(s, sn, p, pn); 7 } 8 9 bool recursive(const char* s, int sn, const char* p, int pn) { 10 if (sn == 0 && pn == 0) return true; 11 if (pn == 0) return false; 12 13 if (*(p + 1) != '