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] == '?'), ifp[j - 1] != '*'; -
P[i][j] = P[i][j - 1] || P[i - 1][j], ifp[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 };
