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