Very concise code in c++, but O(n^2)time


  • 0
    H
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int word_len = words[0].size();
        int step = word_len * words.size();
        if (s.size() < step) return res;
        unordered_map<string, int> map;
        for (auto& w:words) map[w]++;
        for(int i = 0; i < s.size()-step + 1; ++i){
            unordered_map<string, int> map_copy(map.begin(), map.end());
            int j = 0;
            while(j < words.size()){
                string p = s.substr(i+j*word_len, word_len);
                if (map_copy.find(p) != map_copy.end()) {
                    map_copy[p]--;
                    if (map_copy[p] < 0) break;
                }
                else break;
                ++j;
            }
            if (j == words.size())
              res.push_back(i);
        }
        return res;
    }

Log in to reply
 

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