Simple 36ms C++ solution


  • 0
    B
        vector<int> findSubstring(string s, vector<string> &words) {
            if (words.size() < 1) return {};
            using SiMap = unordered_map<string, int>;
            SiMap um;
            for (string &word:words) um[word]++;
            int sz = words[0].size();
    
            vector<int> result;
            vector<SiMap::iterator> v(s.size()); // if we don't allow extra memory, we can just rehash the substring from ilookback
            for (int istep = 0; istep < sz; ++istep) {
                SiMap bs;
                for (int j = istep; j < s.size(); j += sz) {
                    auto found = um.find(s.substr(j, sz));
                    int ilookback = j - (sz * (words.size() - 1));
                    if (found != um.end()) {
                        bs[found->first]++;
                        v[j] = bs.find(found->first);
                        if (ilookback >= 0 and bs == um) {
                            result.push_back(ilookback);
                        }
                    }
    
                    if (ilookback >= 0 and v[ilookback] != SiMap::iterator()) {
                        v[ilookback]->second--;
                    }
                }
            }
    
            return result;
        }
    

    The idea is simple, we basically shift the window of lookup as if we were looking for a substring. each iteration we add a slice to the end, and simultaneously remove the slice from the beginning (think the window as a queue with fixed size) into the window and check if the window of our substring satisfies constraints (correct number of words)


Log in to reply
 

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