Description

Submission

Following is a tricky test case. Since the total length is obviously longer than the string s, the special case can be solved by checking (beg + words[0].size() * words.size()).

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if(words.empty()) return res;

        map<string, int> dict;

        for(auto word : words) {
            auto iter = dict.find(word);
            if(iter == dict.end()) {
                dict.insert(make_pair(word, 1));
            } else {
                dict[word]++;
            }
        }

        int l = words[0].size();
        map<string, int> temp;
        int count = 0;
        int beg = 0;
        for(int i = 0; i <= s.size();) {
            string sub = s.substr(i, l);
            auto dIter = dict.find(sub);

            if(dIter == dict.end()) {
                if(count > 0) {
                    i = beg + 1;
                } else {
                    i++;
                }
                count = 0;
                temp.clear();
            } else {
                auto tIter = temp.find(sub);
                if(tIter == temp.end()) {
                    temp.insert(make_pair(sub, 1));
                } else {
                    temp[sub]++;
                }
                if(count == 0) {
                    beg = i;
                    if(beg + l * words.size() > s.size()) break;
                }
                count++;

                i += l;
                if(temp[sub] > dict[sub]) {
                    temp.clear();
                    i = beg + 1;
                    count = 0;
                } else if(count == words.size()) {
                    res.push_back(beg);
                    count = 0;
                    temp.clear();
                    i = beg + 1;
                }

            }
        }
        return res;
    }
};