题目链接：Multiply Strings
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
这道题的要求是通配符匹配。其中模式串中可以包含‘?’和‘*’，‘?’可以匹配单个任意字符，‘*’可以匹配任意字符串（包括空串）。
1. 递归回溯
看到这道题，首先想到递归回溯处理。
当s和p当前字符相同或者p当前字符为‘?’的时候，说明s和p当前匹配，则s和p同时后移一步。
当p当前字符为‘*’的时候，说明可以匹配任意多个s中的后序子串，因此需要递归s每一种情况，如果成功匹配，返回true；否则，回溯递归检查s的下一子串。
终止条件就是s或p到达字符串尾部。
代码如下，可惜TLE。。。
时间复杂度：O(???)
空间复杂度：O(???)
1 class Solution
2 {
3 public:
4 bool isMatch(const char *s, const char *p)
5 {
6 if(*s == ‘\0‘ && *p == ‘\0‘)
7 return true;
8
9 if(*s == ‘\0‘ || *p == ‘\0‘)
10 return false;
11
12 if(*s == *p || ‘?‘ == *p)
13 return isMatch(++ s, ++ p);
14
15 if(‘*‘ == *p)
16 {
17 int ls = strlen(s), lp = strlen(p);
18 for(int i = 0; i < ls - lp + 1; ++ i)
19 if(isMatch(s + i, p + 1));
20 return true;
21 }
22
23 return false;
24 }
25 };2. 迭代回溯
于是乎考虑非递归进行回溯，即，在s和p右移的时候，当p的当前字符为‘*’时，用ss和pp两个指针记录一下当前位置；当没有匹配的时候，s和p回溯到ss和pp位置的下一位置。就这样直到s到达字符串尾部。
注意一下，当s到达尾部的时候，p可能没有到达尾部。此时需要检测p的剩余字符是否全为‘*’：如果是，返回true；否则，返回false。
AC了。。。
时间复杂度：O(???)
空间复杂度：O(1)
1 class Solution
2 {
3 public:
4 bool isMatch(const char *s, const char *p)
5 {
6 const char *ss = s, *pp = NULL;
7 while(‘\0‘ != *s)
8 {
9 if(‘?‘ == *p || *s == *p)
10 ++ s, ++ p;
11 else if(‘*‘ == *p)
12 ss = s, pp = p ++;
13 else if(pp != NULL)
14 s = ++ ss, p = pp + 1;
15 else
16 return false;
17 }
18
19 while(‘*‘ == *p)
20 ++ p;
21
22 return ‘\0‘ == *p;
23 }
24 };3. 动态规划（一）
当然，这种题，还可以用动态规划的思路处理。用bool型二维数组vvb[i][j]表示s的前i个字符和p的前j个字符是否匹配。
初始值，vvb[0][0]为true，vvb[0][j]的值取决于p前一个位置是否为‘*’以及前一情况是否匹配。
当p[j]等于‘?’或者s[i]等于p[j]时，则vvb[i][j]的值取决于vvb[i-1][j-1]，即为s的前一位置和p的前一位置是否匹配；
当p[j]等于‘*’时，如果该‘*’可以匹配s中的0个或者1个字符，分别对应vvb[i][j-1]，即s的当前位置和p的前一位置是否匹配，以及vvb[i-1][j-1]，即s的前一位置和p的前一位置是否匹配。
可惜MLE，看了数据量不小啊。。。
时间复杂度：O(ls*lp)（ls和lp分别为s和p字符串的长度）
空间复杂度：O(ls*lp)
1 class Solution
2 {
3 public:
4 bool isMatch(const char *s, const char *p)
5 {
6 int ls = strlen(s), lp = strlen(p);
7 vector<vector<bool> > vvb(ls + 1, vector<bool>(lp + 1, false));
8 vvb[0][0] = true;
9
10 for(int j = 1; j <= lp; ++ j)
11 {
12 vvb[0][j] = vvb[0][j - 1] && ‘*‘ == p[j - 1];
13 for(int i = 1; i <= ls; ++ i)
14 {
15 if(‘?‘ == p[j - 1] || s[i - 1] == p[j - 1])
16 vvb[i][j] = vvb[i - 1][j - 1];
17 else if(‘*‘ == p[j - 1])
18 vvb[i][j] = vvb[i][j - 1] || vvb[i - 1][j - 1];
19 }
20 }
21
22 return vvb[ls][lp];
23 }
24 };4. 动态规划（二）
由于判断当前能否匹配的时候，只是用到了前一情况的结果，因此可以申请一维数组vb[i]，表示s的前i个字符和p的前j个字符是否匹配。
当p[j]不是‘*’的时候，只要判断如果当前s[i-1]和p[j-1]上的字符是否匹配，并且vb[i-1]是否为true; 这里可以考虑从后往前遍历s，这样vb[i-1]就是前一情况。
当p[j]是‘*’的时候，因为‘*’可以匹配任意字符串，所以在前面的vb[i]只要有true，那么剩下i后面就都是true了。
还是TLE，因为最后一组数据过不了，好多童鞋选择跳过这组数据了。。。
时间复杂度：O(ls*lp)（ls和lp分别为s和p字符串的长度）
空间复杂度：O(ls*lp)
1 class Solution
2 {
3 public:
4 bool isMatch(const char *s, const char *p)
5 {
6 int ls = strlen(s), lp = strlen(p);
7
8 vector<bool> vb(ls + 1, false);
9 vb[0] = true;
10
11 for(int j = 1; j <= lp; ++ j)
12 {
13 if(‘*‘ != p[j - 1])
14 for(int i = ls; i > 0; -- i)
15 vb[i] = vb[i - 1] && (‘?‘ == p[j - 1] || s[i - 1] == p[j - 1]);
16 else
17 {
18 int i;
19 for(i = 0; i <= ls && !vb[i]; ++ i);
20 for( ; i <= ls; ++ i)
21 vb[i] = true;
22 }
23 vb[0] = vb[0] && ‘*‘ == p[j - 1];
24 }
25
26 return vb[ls];
27 }
28 };4. 贪心法
未完待续。。。
时间复杂度：O()
空间复杂度：O()