30. 串联所有单词的子串 - 力扣（LeetCode）

滑动窗口法，注意窗口大小是固定的，就是words中所有单词的总长度，而words中单词也是等长的。

和这个很像：
leetcode 第 438 题：找到字符串中所有字母异位词(C++)_qq_32523711的博客-CSDN博客

关于滑动窗口;
leetcode 第 76 题：最小覆盖子串(C++)_qq_32523711的博客-CSDN博客

找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置：这句话可以理解为该子串是words中单词的排列，而我们要做的就是找出所有是words中单词排列的子串（的起始位置）。

关于排列;
leetcode 第 567 题：字符串的排列(C++)_qq_32523711的博客-CSDN博客

首先上比较暴力一点的解法，从左到右一个窗口一个窗口的统计，统计使用哈希表，执行效率一般：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {if(s.empty() || words.empty()) return {};vector<int> res;unordered_map<string, int> need, window;for(auto c : words) ++need[c];int len = words[0].size(); //单词长度int len_words = words.size()*len;for(int i = 0; i+len_words <= s.size(); ++i){int count = 0;for(int j = i; j < i+len_words; j += len){auto str = s.substr(j, len);if(need.count(str)){++window[str];if(need[str] == window[str])  ++count;if(need[str] < window[str]) break;}elsebreak;}if(count == need.size()) res.push_back(i);window.clear();}return res;}
};

不过发现了一个易错点:for循环判断条件：

 for(int i = 0; i+len_words <= s.size(); ++i)

不能写为：

 for(int i = 0; i<= s.size() - len_words ; ++i)

原因是s.size()得到无符号数，而int型为有符号的，使用减法会出现溢出（没有深究这儿）。

然后一开始是想套滑动窗口的模板的，但是过程不是那么顺利，因为139个测试用例卡住了：

"ababaab"
["ab","ba","ba"]
输出：[0,1]
预期：[1]

因为我右边界是逐个增加的，所以aba这样的他就认为即会包含ab也会包含ba，所以就错误了，代码认为ababaa是匹配的，但是实际不匹配。所以代码主要错误就是会把一些不匹配的也找出来（当然正确的也能找出来），解决办法嘛，我就又加了一个check函数来判断到底匹不匹配：

但是执行效率还是一般，这个check挺耗时的：

class Solution {
public:bool check(const string &s, unordered_map<string, int> need, int left, int right, int len){int count = 0;for (int i = left; i < right; i = i + len){auto str = s.substr(i, len);if (need.count(str)){--need[str];if (need[str] == 0)	++count;}else return false;}return count == need.size();}vector<int> findSubstring(string s, vector<string>& words) {if(!s.size() || !words.size()) return {};vector<int> res;unordered_map<string, int> need;for(auto c : words) ++need[c];auto test = need;int left = 0, right = 0;int len = words[0].size(); //单词长度int count = 0; //记录需要查全的字符串个数while(right < s.size() - len + 1){auto str = s.substr(right, len);++right; //right右移if(need.count(str) > 0){--need[str];if(need[str] == 0)  ++count;}if(right - 1 - left == (words.size() - 1) * len){if(count == need.size()){if(check(s, test, left, right, len))res.push_back(left);}auto str = s.substr(left, len);++left;if(need.count(str) > 0){if(need[str] == 0)  --count;++need[str];}}}return res;}
};

最后参考了这位兄弟的题解：

串联所有单词的子串 - 串联所有单词的子串 - 力扣（LeetCode）

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {if(s.empty() || words.empty()) return {};vector<int> res;unordered_map<string, int> need;for(auto c : words) ++need[c];int len = words[0].size(); //单词长度int len_words = words.size()*len;//右边界每次增加len，i=0的时候，这一轮就只能遍历到 i+len*n(n为整数) 开头的子串// i 从 0 ～ len-1，就能遍历到所有的子串了for(int i = 0; i < len; ++i){ int left = i, right = i;int count = 0;unordered_map<string, int> window;while(right+len <= s.size()){auto str = s.substr(right, len);right += len;if(need.count(str) == 0){//该单词不在words中，重置计数器、边界以及windowcount = 0;left = right;window.clear();}else{++window[str];++count;while(window[str] > need[str]){ //次数过多也要需要缩小窗口，因为每个单词的次数都应该是刚好的auto tmp = s.substr(left, len);--count;--window[tmp];left += len;}if(count == words.size())    res.push_back(left);}}}return res;}
};