C++ O(n) Solution beats 99%


  • 0
    H

    Main idea is to transform the problem into finding longest sub-array problem. Different offset of the starting position modulo length of word should be considered separately.

    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            int n = s.size();
            int nWords = words.size();
            if (nWords == 0) return vector<int>();
            int len = words[0].size();
            
            unordered_map<string,int> wordMap;
            for (int i = 0, id = 0; i < nWords; ++i) {
                auto it = wordMap.find(words[i]);
                if (it == wordMap.end()) {
                    wordMap.emplace(words[i], id++);
                }
            }
            
            vector<int> wordCount(wordMap.size(), 0);
            for (int i = 0, id = 0; i < nWords; ++i) {
                wordCount[wordMap[words[i]]]++;
            }
            
            vector<int> occur(n, -1);
            for (int i = 0; i < n - len + 1; ++i) {
                auto it = wordMap.find(s.substr(i, len));
                if (it != wordMap.end()) {
                    occur[i] = it->second;
                }
            }
            
            int nDistWords = wordMap.size(); // Number of distinct words
            vector<int> ret;
            
            for (int r = 0; r < len; ++r) {
                vector<int> curWordCount(nDistWords);
                int curLength = 0;
    
                for (int i = r; i < n; i += len) {
                    int index = occur[i];
                    if (index >= 0) {
                        if (curWordCount[index] < wordCount[index]) {
                            ++ curLength;
                            ++ curWordCount[index];
                        } else {
                            while (occur[i - curLength * len] != index) {
                                -- curWordCount[occur[i - curLength * len]];
                                -- curLength;
                            }
                        }
                        
                        if (curLength == nWords)
                            ret.push_back(i - (nWords - 1) * len);
                    } else {
                        if (curLength > 0) {
                            memset(curWordCount.data(), 0, nDistWords * sizeof(int));
                            curLength = 0;
                        }
                    }
                }
            }
            
            return ret;
        }
    };
    

  • 0
    Y

    Looks good. Now I understand why I exceeded time. I did not use map struct to deduplicate the words.


Log in to reply
 

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