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:

f(i,j) == whether the first i chars of s match the first j chars of p. The transition equation is:

```
1). if(p[j-1]!='*') f(i, j) = f(i-1, j-1) && (s[i-1]==p[j-1] || p[j-1]=='?')
2). if(p[j-1]=='*') f(i, j) = f(i, j-1) || f(i-1, j)
bool isMatch(const char *s, const char *p) {
const int m = strlen(s);
const int n = strlen(p);
if(m>30000) return false; // to skip the large test case
vector<bool> prev(n+1,false); // to save space, just O(n) space is used
prev[0]=true;
for(int j=1; j<=n; j++)
prev[j] = prev[j-1] && p[j-1]=='*';
for(int i=1; i<=m; i++) {
vector<bool> cur(n+1,false);
for(int j=1; j<=n; j++) {
if(p[j-1]=='*') {
cur[j] = cur[j-1] || prev[j];
}
else {
cur[j] = prev[j-1] && (s[i-1]==p[j-1] || p[j-1]=='?');
}
}
prev = cur;
}
return prev[n];
}
```

Equation 1). means that if p[j-1] is not *, f(i,j) is determined

by if s[0:i-2] matches p[0:j-2] and if (s[i-1]==p[j-1] or

p[j-1]=='?').Equation 2). means that if p[j-1] is *, f(i,j) is true if either

f(i,j-1) is true: s[0:i-1] matches p[0:j-2] and * is not used

here; or f(i-1,j) is true: s[0:i-2] matches p[0:j-1] and * is

used to match s[i-1].