LeetCode之Regular Expression Matching

【题目】

mplement 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

【分析】

【代码】

/*********************************
*   日期：2014-04-03
*   作者：SJF0115
*   题号: Regular Expression Matching
*   来源：http://oj.leetcode.com/problems/regular-expression-matching/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      using namespace std; class Solution { public: bool isMatch(const char *s, const char *p) { if(s == NULL || p == NULL || *p == '*') { return false; } if(*p == '\0') return *s == '\0'; //next char is not '*': must match current character if(*(p+1) != '*') { if(*s == '\0') return false; if(*p != '.' && *p != *s) return false; return isMatch(s+1,p+1); } //next char is '*' else { int slen = strlen(s); if(isMatch(s,p+2)) return true; for(int i = 0; i < slen; ++i) { if(*p!='.' && *p != *(s+i)) return false; if(isMatch(s+i+1,p+2)) return true; } return false; } } }; int main() { Solution solution; char* s = "abcbcd"; char* p = "ab*bbc"; bool result = solution.isMatch(s,p); cout<