30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

三、优化：

减少了冗余代码，把下列代码优化

ocur_times[first_comout] -= 1;
if (ocur_times[first_comout] == 0) {
    	ocur_times.erase(first_comout);
}

改为：

if (--ocur_times[first_comout] == 0) {
     ocur_times.erase(first_comout);
}

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int words_num = words.size();
        if (words_num < 1 ) {
            return {};
        }
        int word_size = words[0].size();
        int window_length = word_size * words_num;
        if(s.size()<window_length){
            return {};
        }

        for (int bias = 0; bias < word_size && bias < s.size() - window_length + 1; bias++) {
            unordered_map<string, int> ocur_times;
            for (int idx = 0; idx < words_num; idx++) {
                ++ocur_times[s.substr(bias + idx * word_size, word_size)];
            }
            // 和word里面的单词做词频差
            for (auto& w : words) {
                if (--ocur_times[w] == 0) {
                    ocur_times.erase(w);
                }
            }

            // 此时直接在这个哈希表里面移出和移入词组,步长是word_size
            for (int start = bias; start < s.size() - window_length + 1;start += word_size) {
                if (bias != start) {
                    string first_comout = s.substr(start - word_size, word_size);
                    if (--ocur_times[first_comout] == 0) {
                        ocur_times.erase(first_comout);
                    }
                    string next_comin =s.substr(start + window_length - word_size, word_size);
                    if (++ocur_times[next_comin] == 0) {
                        ocur_times.erase(next_comin);
                    }
                }
                if (ocur_times.empty()) {
                    ans.push_back(start);
                }
            }
        }
        return ans;
    }
};

方法二：滑动窗口

还是跟方法一一样
用一个words.size()*words[0].size()的框依次从左边一个个迭代到右边，
但是每次这个框移动words[0].size()的距离，这样就可以利用哈希表，每次都从哈希表里面挤出去一个即将离开的单词，再加入一个新的单词。

为了能把所有情况考虑到，我们不能只移动words[0].size()的距离，还要考虑bias=1，2，3的情况
图示的情况里，bias=2是最后一轮迭代，可知，bias=3的时候，它的第一个迭代就是bias=0的第二个迭代，而这个情况我们已经在bias=0的时候考虑过了

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int words_num = words.size();
        if (words_num < 1 ) {
            return {};
        }
        int word_size = words[0].size();
        int window_length = word_size * words_num;
        if(s.size()<window_length){
            return {};
        }

        for (int bias = 0; bias < word_size &&bias < s.size() - window_length + 1; bias++) {
            unordered_map<string, int> ocur_times;
            for (int idx = 0; idx < words_num; idx++) {
                string window_str = s.substr(bias + idx * word_size, word_size);
                ocur_times[window_str] += 1;
            }
            // 和word里面的单词做词频差
            for (auto& w : words) {
                if (--ocur_times[w] == 0) {
                    ocur_times.erase(w);
                }
            }

            // 此时直接在这个哈希表里面移出和移入词组,步长是word_size
            for (int start = bias; start < s.size() - window_length + 1;
                 start += word_size) {
                if (bias != start) {
                    string first_comout =
                        s.substr(start - word_size, word_size);
                    ocur_times[first_comout] -= 1;
                    if (ocur_times[first_comout] == 0) {
                        ocur_times.erase(first_comout);
                    }
                    string next_comin =
                        s.substr(start + window_length - word_size, word_size);

                    ocur_times[next_comin] += 1;
                    if (ocur_times[next_comin] == 0) {
                        ocur_times.erase(next_comin);
                    }
                }
                if (ocur_times.empty()) {
                    ans.push_back(start);
                }
            }
        }
        return ans;
    }
};

方法一：暴力迭代，180个用例处会超时

用一个words.size()*words[0].size()的框依次从左边一个个迭代到右边，
按照words里面每个词的长度words[0].size()去检测对应单词出现了几次，并维护一个以这些单词为键的哈希表
然后进行判断是否和words里面词频相同

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int words_num = words.size();
        if (words_num < 1 || s.size() < words[0].size() * words_num) {
            return {};
        }
        int word_size = words[0].size();
        int window_length = word_size * words_num;

        for (int bias = 0; bias < s.size() - window_length + 1; bias++) {
            unordered_map<string, int> ocur_times;
            for (int idx = 0; idx < words_num; idx++) {
                string window_str = s.substr(bias + idx * word_size, word_size);
                ocur_times[window_str] += 1;
            }
            for (auto& w : words) {
                if (--ocur_times[w] == 0) {
                    ocur_times.erase(w);
                }
            }
            if (ocur_times.empty()) {
                ans.push_back(bias);
            }
        }
        return ans;
    }
};