C++ 8ms DP with cache and pruning


  • 0
    A
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int ns = s.size(), np = p.size();
            bool dot = false, star = false;
            for (int i = 0; i < np; ++i){
                if (dot && star) break;    // if both '.' and '*' exist already
                if (p[i] == '.') dot = true;
                if (p[i] == '*') star = true;
            }
            if (star == false){
                // no '*' - 1) num of chars must be the same 
                if (ns != np) return false;
                for (int i = 0; i < ns; ++i) {
                    if (p[i] != '.' && p[i] != s[i]) return false;
                }
                return true;
            }
            // there exists '*'
            vector<vector<int>> lookup(ns+1, vector<int>(np+1, -1));
            int res = dp(s, p, lookup, 0, 0);
            return res == 1 ? true : false;
        }
        int dp(string& s, string& p, vector<vector<int>>& lookup, int is, int ip){
            // load from memory, if saved 
            if (lookup[is][ip] == 0 || lookup[is][ip] == 1) return lookup[is][ip];
            // otherwise
            int ns = s.size(), np = p.size();
            if (is == ns) {
                if (ip == np) return lookup[is][ip] = 1;
                // ip < np
                int tmp = ip;
                while (tmp + 1 < np){
                    if (p[tmp] != '*' && p[tmp+1] == '*') tmp += 2;
                    else return lookup[is][ip] = 0;
                }
                return lookup[is][ip] = tmp == np - 1 ? 0 : 1;
            }
            if (ip == np) return lookup[is][ip] = 0;
            // is != ns and ip != np
            while (is < ns && ip < np - 1 && p[ip + 1] != '*'){
                if (s[is] != p[ip] && p[ip] != '.') return lookup[is][ip] = 0;
                ++is; ++ip;
            }
            if (is == ns) return lookup[is][ip] = dp(s, p, lookup, is, ip);
            // is < ns
            if (ip == np - 1) {
                if (is != ns - 1) return lookup[is][ip] = 0;
                if (s[is] != p[ip] && p[ip] != '.') return lookup[is][ip] = 0;
                return lookup[is][ip] = 1;
            }
            // ip < np - 1 && is < ns && p[ip+1] == '*'
            if (s[is] != p[ip] && p[ip] != '.') {
                return lookup[is][ip] = dp(s, p, lookup, is, ip+2);
            }
            // s[is] == p[ip]
            int pos = is, duplicates = 1;
            while (pos + 1 < ns && s[pos+1] == s[is]) {
                ++pos; ++duplicates;
            }
            if (p[ip] != '.'){
                for (int j = is; j <= is + duplicates; ++j){
                    int tmp = dp(s, p, lookup, j, ip + 2);
                    if (tmp) return lookup[is][ip] = 1;
                }            
            }
            else{
                for (int j = is; j <= ns; ++j){
                    int tmp = dp(s, p, lookup, j, ip+2);
                    if (tmp) return lookup[is][ip] = 1;
                }
            }
            return lookup[is][ip] = 0;
        }
    };

Log in to reply
 

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