C++ DP solution
It seems that only Greedy solution can pass all test cases (sorry if I omit any DP solution that passes all test cases). My DP solution also fails to pass the s
It seems that only Greedy solution can pass all test cases (sorry if I omit any DP solution that passes all test cases). My DP solution also fails to pass the s=aaaaaaaaaaaaaa.............. (lots of a's...). However, despite this very large case my DP solution passes all other cases. The idea is:\n\nf(i,j) == whether the first i chars of s match the first j chars of p. The transition equation is:\n\n    1). if(p[j-1]!='*') f(i, j) = f(i-1, j-1) && (s[i-1]==p[j-1] || p[j-1]=='?')\n\n    2). if(p[j-1]=='*') f(i, j) = f(i, j-1) || f(i-1, j)\n\n    bool isMatch(const char *s, const char *p) {\n        const int m = strlen(s);\n        const int n = strlen(p);\n        if(m>30000) return false; // to skip the large test case\n        vector<bool> prev(n+1,false); // to save space, just O(n) space is used\n        prev[0]=true;\n        for(int j=1; j<=n; j++)\n            prev[j] = prev[j-1] && p[j-1]=='*';\n        for(int i=1; i<=m; i++) {\n            vector<bool> cur(n+1,false);\n            for(int j=1; j<=n; j++) {\n                if(p[j-1]=='*') {\n                    cur[j] = cur[j-1] || prev[j];\n                }\n                else {\n                    cur[j] = prev[j-1] && (s[i-1]==p[j-1] || p[j-1]=='?');\n                }\n            }\n            prev = cur;\n        }\n        return prev[n];\n    }\n\n> Equation 1). means that if p[j-1] is not *, f(i,j) is determined\n> by if s[0:i-2] matches p[0:j-2] and if (s[i-1]==p[j-1] or\n> p[j-1]=='?'). \n> \n> Equation 2). means that if p[j-1] is *, f(i,j) is true if either\n> f(i,j-1) is true: s[0:i-1] matches p[0:j-2] and * is not used\n> here; or f(i-1,j) is true: s[0:i-2] matches p[0:j-1] and * is\n> used to match s[i-1].
[]