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


  • 0
    E
    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];
    }
    

    };


  • 1
    C

    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.


Log in to reply
 

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