Accepted C++ DP Solution with a Trick
Updated: Since the OJ has relaxed the time constraint, the following DP solution is now accepted without the trick :-) \n\nWell, so many people has tried to sol
**Updated**: Since the OJ has relaxed the time constraint, the following DP solution is now accepted without the trick :-) \n\nWell, 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 :-) \n\nLet'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: \n\n 1. `P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?')`, if `p[j - 1] != '*'`;\n 2. `P[i][j] = P[i][j - 1] || P[i - 1][j]`, if `p[j - 1] == '*'`.\n\nIf you feel confused with the second equation, you may refer to [this link][1]. There is an explanation in the comments.\n\nWe optimize the DP code to `O(m)` space by recording `P[i - 1][j - 1]` using a single variable `pre`.\n\nThe trick to avoid TLE is to hard-code the result for the largest test case by \n\n    if (n > 30000) return false;  \n\nThe complete code is as follows.\n\n    class Solution {\n    public:\n        bool isMatch(string s, string p) { \n            int m = s.length(), n = p.length();\n            if (n > 30000) return false; // the trick\n            vector<bool> cur(m + 1, false); \n            cur[0] = true;\n            for (int j = 1; j <= n; j++) {\n                bool pre = cur[0]; // use the value before update\n                cur[0] = cur[0] && p[j - 1] == '*'; \n                for (int i = 1; i <= m; i++) {\n                    bool temp = cur[i]; // record the value before update\n                    if (p[j - 1] != '*')\n                        cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');\n                    else cur[i] = cur[i - 1] || cur[i];\n                    pre = temp;\n                }\n            }\n            return cur[m]; \n        }\n    };\n\nFor those interested in a fully correct solution, [this link][2] has a nice Greedy solution. And I have rewritten the code below to fit the new C++ interface (changed from `char*` to `string`).\n\n    class Solution {\n    public:\n        bool isMatch(string s, string p) {\n            int m = s.length(), n = p.length();\n            int i = 0, j = 0, asterisk = -1, match;\n            while (i < m) {\n                if (j < n && p[j] == '*') {\n                    match = i; \n                    asterisk = j++;\n                }\n                else if (j < n && (s[i] == p[j] || p[j] == '?')) {\n                    i++; \n                    j++;\n                }\n                else if (asterisk >= 0) {\n                    i = ++match;\n                    j = asterisk + 1;\n                }\n                else return false;\n            }\n            while (j < n && p[j] == '*') j++;\n            return j == n;\n        }\n    };\n\n  [1]: https://leetcode.com/discuss/21634/c-dp-solution\n  [2]: https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution
['Dynamic Programming', 'C++']