Wildcard Matching

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") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

思路：
参考链接：http://blog.csdn.net/a83610312/article/details/9750655
链接里面的内容有很多学习的地方，其中最重要的是遇到问题时不一定第一时间找到最终解决方案，但是可以通过不断地改进自己的方法来达到目的，戒骄戒躁。在解决任何问题的时候都应该有这样的心态，过程也很重要。
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 == '')
 3             return *s == '';
 4         if(*s == ''){
 5             while(*p == '*')
 6                 p++;
 7             return *p == '';
 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             else
20                 wordNum[i] = wordNum[i-1];
21         }
22         vector<vector<bool> > matchTable(2, vector<bool>(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                 else
40                     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 == '')
 3             return *s == '';
 4         if(*s == '') {
 5             while(*p == '*')
 6                 p++;
 7             return *p == '';
 8         }
 9         const char *lastS = NULL, *lastP = NULL;
10         while(*s != ''){
11             if(*s == *p || *p == '?'){
12                 s++;
13                 p++;
14             }
15             else if(*p == '*'){
16                 while(*p == '*')
17                     p++;
18                 if(*p == '')
19                     return true;
20                 lastP = p;
21                 lastS = s;
22             }
23             else if((*s != *p || *p == '') && lastP != NULL){
24                 p = lastP;
25                 s = lastS+1;
26                 lastS++;
27             }
28             else
29                 return false;
30         }
31         while(*p == '*')
32             p++;
33         return *p=='';
34     }