Share my 54ms solution


  • 2
    X

    based on rolling hash, plus multi-window, here is my 54ms solution.

    class Solution {
    public:
        vector<int> findSubstring(string S, vector<string> &L) {
            vector<int> result;
            if (L.empty() || L[0].empty() ) return result;
            if (S.size() < L.size() * L[0].size()) return result;
    
            const int lsize = L.size();
            const int wsize = L[0].size();
            const int gsize = lsize * wsize;
            const int r = 31;
            const int q = 997;
            const int m = 3355439;
    
            int lhash = 0;
            for (int i = 0; i<lsize; i++) {
                    int whash = 0;
                    for (int j=0; j<wsize; j++) {
                            whash = (whash * r + L[i][j]) % q;
                    }
                    lhash = (lhash + whash) % m;
            }
    
            vector<int > ghashes(wsize);
            vector<int> window(gsize);
            int whead = 0;
    
            int whash = 0;
            int i = 0;
            int weight = 1;
            for (; i<wsize-1; i++) {
                    whash = (whash * r + S[i]) % q;
                    weight = (weight * r) % q;
            }
    
            unordered_multiset<string> Lset(L.begin(), L.end());
            for (; i<S.size(); i++) {
                    int &ghash = ghashes[whead % wsize];
                    ghash = (ghash - window[whead] + m) % m;
                    window[whead] = whash = (whash * r + S[i]) % q;
                    ghash = (ghash + whash) % m;
                    whead = ++whead % gsize;
                    whash = (whash - (S[i-wsize+1] * weight) % q + q) % q;
    
                    if (ghash == lhash && match(S, i-gsize+1, Lset))
                            result.push_back(i - gsize + 1);
            }
    
            return result;
        }
        
        bool match(const string &S, int pos, unordered_multiset<string> L) {
            if (pos < 0) return false;
    
            const int lsize = L.size();
            const int wsize = L.begin()->size();
            for (int i=0; i<lsize; i++) {
                    auto iter = L.find(S.substr(pos, wsize));
                    if (iter == L.end()) return false;
                    L.erase(iter);
                    pos += wsize;
            }
            return true;
        }
    };

Log in to reply
 

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