[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:

P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
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 };