本文主要是介绍*LeetCode Wildcard Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/wildcard-matching/
方法一：DFS （需要开数组判重）
这里我得承认，作弊了点，，因为有一组数据，长度4100左右两个字符串匹配。 所以开数组大小其实是WA了一次 然后才确定大小的，，，，想想为什么需要判重：
s=aaaaa
p=a**a
dfs(s-2,p-2)可能通过多种途径到达，这样的话每种途径都Dfs一次后面的，会TLE
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>using namespace std;const int SIZE = 4100+1;
char vis[SIZE][SIZE];class Solution {
public:bool isMatch(string s, string p) {int ptrs = 0, ptrp = 0;for(int i=0;i<s.size();i++)for(int j=0;j<p.size();j++) {vis[i][j] = -1;}return match(s,p, ptrs, ptrp);}bool judge(string p, int ptrp) {int flag = 1;for(int i=ptrp;i<p.size();i++)if( p[i] != '*' ) {flag = 0;break;}return flag;}bool match(string s, string p, int ptrs, int ptrp) {if(ptrs >= s.size()) {if(ptrp>=p.size() || judge(p, ptrp) )return true;elsereturn false;}if(ptrp >= p.size()) return false;if(p[ptrp] == s[ptrs] || p[ptrp] == '?') {while(ptrp<p.size() && ptrs<s.size() && (p[ptrp] == s[ptrs] || p[ptrp] == '?')){ptrs++, ptrp++;}return match(s, p, ptrs, ptrp);} else {if(p[ptrp] == '*') {return matchStar(s, p, ptrs, ptrp);} else {return false;}}}bool matchStar(string s, string p, int ptrs, int ptrp) {int flag = 0;while(ptrs<s.size() ) {if( vis[ptrs][ptrp]==-1 ) {vis[ptrs][ptrp] = match(s,p,ptrs, ptrp+1); // 相当于枚举匹配的个数,从0个开始}if(vis[ptrs][ptrp] == 1) return true;ptrs++;}return match(s,p,ptrs, ptrp+1);}
};int main() {freopen("44.txt", "r", stdin);string s,p;while( cin >> s >> p ) {Solution ss;cout << ss.isMatch(s, p) << endl;}return 0;
}方法二：
这个代码好巧妙 ，，， 还有点不是很理解
class Solution{public:bool isMatch(string s , string p) {return Match(s.c_str(), p.c_str());}bool Match(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) //pp相当于*的位置,也就是当不符合匹配的情况，如果是*可以继续s++s = ++ ss, p = pp + 1;elsereturn false;}while('*' == *p)++ p;return '\0' == *p;}
};这里还有两种过不掉的（TLE）的方法
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 };5. 贪心法
未完待续。。。
时间复杂度：O()
空间复杂度：O()
这篇关于*LeetCode Wildcard Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
