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

题目是让我们自己实现正则表达式中* 和 . 的匹配功能 

. 匹配任意的一个字符

*  如a*是一个整体，表示有 0个a 或 1个a 或 2个a 或..... 任意多个a 

如果是 .*可以匹配 0个任意字符 或一个任意字符 或 任意多个任意字符 但这些字符必须是相同的。

 

思路：

开始觉的跟差不多，后来发现不一样，里面*可以随意匹配，所以当遇到后面一个*之后，前面的*就可以不用管了。

而现在这道题，*只能匹配重复的字符，所以必须考虑多个*表示的范围，所以，问题的关键就在于每个 x*都表示了多少字符。

很容易想到递归，可是写完递归后我在提交的时候各种特殊情况都通不过，每次都对特殊情况加代码，结果越加越长，加到70行仍然没AC。我默默的知道我的思路肯定是有问题了...

 

看大神的代码，我终于知道问题在哪了。

因为我每次都是一个字符一个字符判断的，这样遇到*之后还需要判断很多*前一个字符的情况。

但大神每次都是针对p 2个字符为一组来判断的 根据*(p+1) == '*' 来区分不同的情况，一下子就容易了很多。

还有，大神的代码凡是遇到返回值是真的情况就返回答案，不再递归

class Solution {public:    bool matchFirst(const char *s, const char *p){        return (*p == *s || (*p == '.' && *s != '\0'));    }　　bool isMatch(const char *s, const char *p) {   　　 if (*p == '\0') return *s == '\0';  //empty　　   　　 if (*(p + 1) != '*') {
   //without *      　　  if(!matchFirst(s,p)) return false;        　　return isMatch(s + 1, p + 1);    　　} else { //next: with a *       　　 if(isMatch(s, p + 2)) return true;    //try the length of 0       　　 while ( matchFirst(s,p) )       //try all possible lengths           　　  if (isMatch(++s, p + 2))return true;    　　}　　}};

 

动态规划的方法：

用dp[i][j]表示 s[0 ~ i-1] 与 p[0 ~ j - 1] 匹配的情况， 可以匹配时true 反之为 false

那么dp[i][j]只会在以下4种情况下为真：

①dp[i-1][j-1]为真，并且s[i-1]与p[j-1]匹配

②dp[i][j-1]为真，并且p[j-1]=='*'

③dp[i-1][j]为真, 并且p[j-1]=='*' 并且 p[j-2]与s[i-1]匹配

④dp[i][j-2]为真，并且p[j-1]=='*'

边界：

dp[0][0] 都是空的肯定为真

dp[i][0] 字符串非空，匹配串为空，肯定为假

dp[0][j] 字符串空，匹配串非空，若p[j-1] == '*' 并且 dp[0][j-2]为真 的情况下 为真

代码是我参照大神的思路写的。

class Solution {public:bool isMatch(const char *s, const char *p)    {        int m = strlen(s);        int n = strlen(p);        vector
     
      
       > dp(m+1, vector
       
        (n+1, false));        dp[0][0] = true;        for(int i = 1; i <= m; i++)        {            dp[i][0] = false;        }        for(int j = 1; j <= n; j++)        {            dp[0][j] = (p[j-1] == '*') && (j >= 2) && dp[0][j-2]; //第j个字符在p中的下标是j-1，因为是从0开始的        }        for(int i = 1; i <= m; i++)        {            for(int j = 1; j <= n; j++)            {                dp[i][j] = (dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.'))                       ||  (dp[i][j-1] && (p[j-1] == '*'))                       ||  (dp[i-1][j] && p[j-1] == '*' && ((j >= 2) && s[i-1] == p[j-2] || p[j-2] == '.'))                       ||  ((j >= 2) && dp[i][j-2] && (p[j-1] == '*'));            }        }        return dp[m][n];    }};