My C++ code with HashTable with Queue for O(n) runtime, 71ms runtime


  • 4
    H

    I would like share my linear solution with HashTable and Queue with runtime only 71ms. The Queue is used to store the last appearance position of the first word of that type. You need to update the Queue each time.

    vector<int> findSubstring(string S, vector<string> &L) {
            vector<int> res;
            if (L.size() == 0) return res;
            if (S.size() == 0) return res;
            int wordLen = L[0].size();
            if (S.size() < wordLen) return res;
            
            unordered_map<string, queue<int> > wordhash; // word and appearing positions.
            unordered_map<string, queue<int> >::iterator it;
            queue<int> Q;
            Q.push(-1);
            for (int i = 0; i<L.size(); ++i) {
                it = wordhash.find(L[i]);
                if (it == wordhash.end()) {
                    wordhash[L[i]] = Q;
                } else {
                    it->second.push(-1);
                }
            }
            unordered_map<string, queue<int> > temp = wordhash;
            for (int i = 0; i<wordLen; ++i) {
                int currWordCnt = 0;
                wordhash = temp;
                for (int index = i; index<=S.size()-wordLen; index += wordLen) {
                    it = wordhash.find(S.substr(index, wordLen));
                    if (it == wordhash.end()) {
                        currWordCnt = 0;
                    } else {
                        int lastPos = it->second.front();
                        if (lastPos == -1) {
                            currWordCnt++;
                        } else if (currWordCnt*wordLen < index-lastPos) {
                            currWordCnt++;
                        } else {
                            currWordCnt = (index-lastPos)/wordLen;
                        }
                        it->second.pop();
                        it->second.push(index);
                        if (currWordCnt == L.size()) {
                            res.push_back(index-wordLen*(L.size()-1));
                        }
                    }
                }
            }
            return res;
        }

  • 0
    R

    I think the time complexity of this algorithm is O(wordlen*n)


Log in to reply
 

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