a 3ms brute force method


  • 0
    S
    class Solution {
    public:
        bool isMatch(string s, string p) {
            return isMatch(s.c_str(), s.size(), p.c_str());
        }
        
        bool isMatch(const char* ps, int ps_size, const char *pp) {
            if (!ps[0] && !pp[0]) return true;
            if (!pp[0]) return false;
            
            const char *p = pp;
            int nr_dots = 0;
            
            while (1) {
                if (p[1] == '*') 
                    p += 2;
                else if (p[0] == '.') {
                    ++ p;
                    ++ nr_dots;
                }
                else
                    break;
            }
             if (nr_dots > ps_size) return false;
            string sub1(pp, 0, p - pp);
            
            for (;*p != 0 && *p != '.' && *p != '*'; ++ p)
                ;
            if (*p == '*') 
                --p;
            string sub2(pp, sub1.size(), p - pp - sub1.size());
            
            const char *src = ps + nr_dots - 1;
            if (sub2.empty()) {
                return isMatchAsterisk(ps, ps + ps_size, sub1);
            }
            
           // cout << "sub1: " << sub1 << "\nsub2: " << sub2 << endl;
            while (1) {
                src = strstr(src + 1, sub2.c_str());
                if (!src) return false;
                if (!isMatchAsterisk(ps, src, sub1)) return false;
                if (isMatch(src + sub2.size(), p)) return true;
            };
          
            return false;
        }
        
        bool isMatchAsterisk(const char *ps1, const char *ps2, string &sub) {
    
            for (int i = 0; i < sub.size(); ++ i) {
                if (sub[i + 1] == '*') {
                    if (sub[i] == '.') return true;
                    while (*ps1 == sub[i]) ++ ps1;
                    ++ i;
                } else 
                    ++ ps1;
                    
                if (ps1 >= ps2) return true;   
            }
            return ps1 >= ps2;
        }
    
    }
    

Log in to reply
 

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