# The complexity is O(NM), but get a TLE. Can anybody help me?

• ``````class Solution

{
public:
bool isMatch(const char *s, const char *p) {
int lens = strlen(s);
int lenp = strlen(p);
vector<vector<bool> > f(2, vector<bool>(lens + 1, false));
f[0][0] = true;
int flag = 1;
for (int i = 0; i < lenp; ++i) {
if (p[i] == '*') {
for (int j = 0; j < lens; ++j) {
if (f[!flag][j + 1]) {
for (int k = j; k < lens; ++k)
f[flag][k + 1] = true;
break;
}
}
} else {
for (int j = 0; j < lens; ++j) {
if (p[i] == '?') {
f[flag][j + 1] = f[!flag][j];
} else if (p[i] != '*') {
f[flag][j + 1] = f[!flag][j] && p[i] == s[j];
}
}
f[flag][0] = false;
}

flag = !flag;

}

return f[!flag][lens];

}
};
``````

The code above gets TLE. But the code below can gets ACC. I think the complexity is the same.

``````class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (!*s && !*p) return true;

int ms_max = 1;//size of *s
const char* ss = s;
while(*ss){ ++ms_max;++ss;}
int np_max = 1;
const char* pp = p;
while(*pp){if(*pp!='*')++np_max;++pp;}
if(ms_max < np_max) return false;

vector<vector<bool> > r(2, vector<bool>(ms_max, false));
bool flag = 1;
r[0][0] = true;
do{//*p
int ms = 1;
ss = s;
if (*p == '*'){
while(*p == '*') ++p;
--p;
r[flag][0] = r[!flag][0];
for( ;ms <= ms_max; ++ms){//up and left
if (r[!flag][ms] || r[flag][ms-1]) break;
else r[flag][ms] = false;
}
for(;ms <= ms_max; ++ms){
r[flag][ms] = true;
}
}
else{
do{
bool r_flag = false;
if (*ss == *p || *p == '?'){
r_flag = r[!flag][ms-1];//diagnal
}
r[flag][ms]=r_flag;
++ms;++ss;
}while(*ss);//*s
r[flag][0] = false;
}
++p;
flag = !flag;
}while(*p);
return r[!flag][ms_max-1];
}
``````

};

• The secret is:

The second solution checks an obvious situation ahead of time. That is, if p has more non-'* ' characters than the total number of characters in s, then they for sure are not going to match, and you can avoid running the lengthy len(p)*len(s) loop.

This saves time on one of the long string tests in OJ.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.