8 ms c++, simple and fast with RE compression


  • -1
    B
    class Solution {
    public:
        bool isMatch(string s, string p) {
            p = compress(p);
            return isMatch(s, 0, p, 0);
        }
        bool isMatch(string& s, int s_index, string& p, int p_index){
            if (p_index == p.size()) return s_index == s.size();
            if (p_index + 1 < p.size() && p[p_index+1] == '*'){
                if (isMatch(s, s_index, p, p_index + 2)) return true;
                for(int i = s_index; i < s.size(); ++i){
                    if (s[i] == p[p_index] || p[p_index] == '.'){
                        if (isMatch(s, i+1, p, p_index + 2)) return true;
                    }else {
                        break;
                    }
                }
                return false;
            } else {
                return s_index < s.size() && p_index < p.size() && (p[p_index] == s[s_index] || p[p_index] == '.') && isMatch(s, s_index + 1, p, p_index + 1);
            }
        }
        string compress(string& p){
            char* buf = (char*)malloc(p.size() * sizeof(char));
            char* cur = buf;
            for(int i = 0; i < p.size(); ++i){
                *cur++ = p[i];
                if (p[i] == '*' && i+ 2 < (int)p.size() && p[i+1] == p[i-1] && p[i+2] == '*'){
                    i += 2;
                }
            }
            string res(buf, cur - buf);
            delete buf;
            return res;
        }
    };

  • 0
    V

    thanks for sharing,it's more faster when using compress;


Log in to reply
 

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