Regular Expression Matching

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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  zero or more

思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。

代码：

 class Solution {  
 public:  
   bool isMatch(const char *s, const char *p) {  
     if (*p == '\0') return *s == '\0';  
     if (*(p+1) == '*') {  
       if (isMatch(s, p+2)) return true; // match 0  
       while (*s && (*s == *p || *p == '.')) { // match 1,2,...  
         if (isMatch(s+1, p+2)) return true;  
         s++;  
       }  
     } else if (*s && (*p == *s || *p == '.') && isMatch(s+1, p+1)) // always check *s  
         return true;  
     return false;  
   }  
 };  
   
 // dp solution  
 class Solution {  
 public:  
   bool isMatch(const char* s, const char* p) {  
     if (*p == '\0') return *s == '\0';  
     int M = strlen(s), N = strlen(p);  
     vector<vector<bool> > dp(M+1, vector<bool>(N+1, false)); // 前i个字符in s和前j个字符in p的匹配  
     dp[0][0] = true;  
     for (int j = 0; j < N; ++j)  
       dp[0][j+1] = p[j] == '*' ? (j >= 1 && dp[0][j-1]) : false;   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (s[i] == p[j] || p[j] == '.') {  
           dp[i+1][j+1] = dp[i][j];  
         } else if (p[j] == '*') {  
           dp[i+1][j+1] = dp[i+1][j-1] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i][j+1]);  
         }  
       }  
     }  
     return dp[M][N];  
   }  
 };