Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.'*' Matches any sequence of characters (including the empty sequence).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", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false 思路： 参考链接： 链接里面的内容有很多学习的地方，其中最重要的是遇到问题时不一定第一时间找到最终解决方案，但是可以通过不断地改进自己的方法来达到目的，戒骄戒躁。在解决任何问题的时候都应该有这样的心态，过程也很重要。 1、首先想到这题和Regular Expression Match很相似，可以用递归，但是这题中的*可以匹配任意字符，而不是正则表达式中的前一个字符，所以搜索空间更大，出现TLE。 2、于是转到DP。然而测试数据中s和p可能很长，用O(length(s)*length(p))的空间的话会出现MLE。 3、最后在DP基础上压缩空间，用两个一维的数组代替原来的多维数组，空间变成O(length(p))。因为每一层遍历只需要用到上一层的结果，所以可以压缩空间。这种空间压缩的方法在别的DP中也可以考虑使用。 代码如下：

1     bool isMatch(const char *s, const char *p) { 2         if(*p == '\0') 3             return *s == '\0'; 4         if(*s == '\0'){ 5             while(*p == '*') 6                 p++; 7             return *p == '\0'; 8         } 9         int lp = strlen(p), ls = strlen(s);10         string tp = p;11         if(ls < lp-count(tp.begin(), tp.end(), '*'))12             return false;13         int wordNum[lp];14         wordNum[0] = (*p != '*');15         int i, j;16         for(i = 1; i < lp; i++){17             if(p[i] != '*')18                 wordNum[i] = wordNum[i-1]+1;19             else20                 wordNum[i] = wordNum[i-1];21         }22         vector
     
      
        > matchTable(2, vector
       
        (lp, false));23         for(i = 0; wordNum[i] == 0; i++)24             matchTable[0][i] = true;25         if(i < lp && (s[0] == p[i] || p[i] == '?')){26             for(i; wordNum[i] == 1; i++)27                 matchTable[0][i] = true;28         }29         int cur, last;30         for(i = 1; i < ls; i++){31             cur = i%2;32             last = (i+1)%2;33             matchTable[cur][0] = (*p == '*');34             for(j = 1; j < lp; j++){35                 if(s[i] == p[j] || p[j] == '?')36                     matchTable[cur][j] = matchTable[last][j-1];37                 else if(p[j] == '*')38                     matchTable[cur][j] = matchTable[cur][j-1] || matchTable[last][j-1] || matchTable[last][j];39                 else40                     matchTable[cur][j] = false;41             }42         }43         return matchTable[(ls-1)%2][lp-1];44     }
       
      
     

 

此外，还有一种贪心的方法。用s和p进行比对，如果*s等于*p或者*p等于'?'，则s++,p++;如果*p等于'*'，记录当前*所在位置的下一个位置（如果有多个连续的*，找到最后一个*），从下一个位置开始匹配；如果匹配失效，那么回到上次记录的位置，将s加一，表示*代替s的一个字符。这种方法的证明还没想明白，但是速度是最快的。 代码如下：

1     bool isMatch(const char *s, const char *p) { 2         if(*p == '\0') 3             return *s == '\0'; 4         if(*s == '\0') { 5             while(*p == '*') 6                 p++; 7             return *p == '\0'; 8         } 9         const char *lastS = NULL, *lastP = NULL;10         while(*s != '\0'){11             if(*s == *p || *p == '?'){12                 s++;13                 p++;14             }15             else if(*p == '*'){16                 while(*p == '*')17                     p++;18                 if(*p == '\0')19                     return true;20                 lastP = p;21                 lastS = s;22             }23             else if((*s != *p || *p == '\0') && lastP != NULL){24                 p = lastP;25                 s = lastS+1;26                 lastS++;27             }28             else29                 return false;30         }31         while(*p == '*')32             p++;33         return *p=='\0';34     }