[C++] unordered_map, unordered_set, substr

 

LeetCode: 30. Substring with Concatenation of All Words

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150 

Substring with Concatenation of All Words - LeetCode

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int length = words.at(0).size();
        for (int t = 0; t < length; t++) {
            unordered_map<string, int> needs;
            unordered_set<string> wordSet(words.begin(), words.end());
            unordered_set<string> requireds(wordSet);
            for (string word : words) {
                if (needs.count(word) == 0) {
                    needs[word] = 1;
                }
                else {
                    needs[word]++;
                }
            }
            for (int i, j = t; j < s.size(); j += length) {
                i = j - length * words.size();
                if (i >= 0) {
                    string word = s.substr(i, length);
                    if (wordSet.find(word) != wordSet.end()) {
                        needs[word]++;
                        if (needs[word] > 0) {
                            requireds.insert(word);
                        }
                    }
                }
                string word = s.substr(j, length);
                if (wordSet.find(word) != wordSet.end()) {
                    needs[word]--;
                    if (needs[word] == 0) {
                        requireds.erase(word);
                    }
                    if (requireds.empty()) {
                        ret.push_back(i + length);
                    }
                }
            }
        }
        return ret;
    }
};