# [LeetCode] Wildcard Matching

Well, so many people has tried to solve this problem using DP. And almost all of them get TLE (if you see a C++ DP solution that gets accepted, please let me know ^_^). Well, this post aims at providing an accpted DP solution which uses a trick to get around the largest test case, insteaed of a solution that is fully correct. So please do not give me down votes for that :-)

Let's briefly summarize the idea of DP. We define the state P[i][j] to be whether s[0..i)matches p[0..j). The state equations are as follows:

1. P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
2. P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.

If you feel confused with the second equation, you may refer to this link. There is an explanation in the comments.

We optimize the DP code to O(m) space by recording P[i - 1][j - 1] using a single variablepre.

The trick to avoid TLE is to hard-code the result for the largest test case by

if (n > 30000) return false;

The complete code is as follows.

 1 class Solution {
2 public:
3     bool isMatch(string s, string p) {
4         int m = s.length(), n = p.length();
5         if (n > 30000) return false; // the trick
6         vector<bool> cur(m + 1, false);
7         cur[0] = true;
8         for (int j = 1; j <= n; j++) {
9             bool pre = cur[0]; // use the value before update
10             cur[0] = cur[0] && p[j - 1] == '*';
11             for (int i = 1; i <= m; i++) {
12                 bool temp = cur[i]; // record the value before update
13                 if (p[j - 1] != '*')
14                     cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
15                 else cur[i] = cur[i - 1] || cur[i];
16                 pre = temp;
17             }
18         }
19         return cur[m];
20     }
21 };

For those interested in a fully correct solution, this link has a nice Greedy solution. And I have rewritten the code below to fit the new C++ interface (changed from char* to string).

 1 class Solution {
2 public:
3     bool isMatch(string s, string p) {
4         int m = s.length(), n = p.length();
5         int i = 0, j = 0, asterisk = -1, match;
6         while (i < m) {
7             if (j < n && p[j] == '*') {
8                 match = i;
9                 asterisk = j++;
10             }
11             else if (j < n && (s[i] == p[j] || p[j] == '?')) {
12                 i++;
13                 j++;
14             }
15             else if (asterisk >= 0) {
16                 i = ++match;
17                 j = asterisk + 1;
18             }
19             else return false;
20         }
21         while (j < n && p[j] == '*') j++;
22         return j == n;
23     }
24 };

|

LeetCode 44. Wildcard Matching

73 0
|

LeetCode - 44. Wildcard Matching
44. Wildcard Matching  Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个字符串和一个自动机，问你自动机可否接收这个字符串.
1202 0
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
29 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
35 2
|
1月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
25 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
23 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
27 1
|
1月前
【LeetCode刷题】专题三：二分查找模板
【LeetCode刷题】专题三：二分查找模板
16 0
|
1月前
【LeetCode刷题】前缀和解决问题：742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题：742.寻找数组的中心下标、238.除自身以外数组的乘积
26 0