题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）
解题思路：这道题我用了一个暴力解法，就是利用两个unordered_map，一个用来记录words中的string，一个用来保存从某个下标开始的临时的string，最后对比两个unordered_map是否相同，如果相同的话，就把这个开始的下标插入到vector中，一直循环，直到遍历完下标。
具体细节请参考以下代码，已附上详细的解释，相信各位小伙伴都能看懂并学会这道题的。
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> v; //无论s为空还是words为空，都不会有符合题意的下标，直接返回即可 if (s.empty() || words.empty()) { return v; } int n = words.size(); int m = words[0].size(); //根据题意，s中的字符的数量必须大于words中所有字符相加 //例如：words为["foo","bar"],那么m*n就是6，则s.size() //必须要大于等于6才有满足题意的可能性 if (s.size() < m * n) { return v; } //创建两个unordered_map unordered_map<string, int> umap; unordered_map<string, int> tmp; //把words中的字符插入到umap中 for (auto& e : words) { umap[e]++; } int i = 0; int j = 0; //这里的循环条件是i+m*n<=s.size()，一定要去等于，因为i本身是下标， //而m和n是字符串的size，假设s为"barfoothefoobarman"， // words为["foo","bar"]，则s.size()为18，那么它的下标取值范围 // 就是[0,17]，当i=12的时候，i+m*n = 12+2*3 = 18 = s.size()， //但是这个i从12到17依然有6个字符，依然符合题意，所以当i+m*n=s.size() //时，循环仍然要继续进行 for (i = 0; i + m * n <= s.size(); i++) { //j从i下标开始，每次往后取s中的m个字符，由于j下标，所以j要小于i + m * n //j每一次迭代的距离是m个字符，m为words中每一个元素的长度 for (j = i; j < i + m * n; j += m) { //从j位置开始往后取m个字符 string str = s.substr(j, m); //words中所有的string都已经插入到umap中，所以在umap中查找str if (umap.find(str) == umap.end()) { //如果在umap中没有找到str，说明从i下标开始往后找的m*n个字符中 //找不到words中的所有string，此时可以排除这个i了，直接break break; } //如果找到了str，那把这个str保存到tmp中，继续往后找 tmp[str]++; } //如果j==i+m*n，说明循环不是break出来的，每一次的str都找到并插入到 //了tmp中，此时再判断umap和tmp是否相等，如果相等，那么说明从i开始 //往后找到的m*n个字符是符合题意的串联所有单词的子串，这个i就是起始位置 //保存这个i if (j == i + m * n && umap == tmp) { v.push_back(i); } //一次循环结束之后一定要记得清空临时的tmp，防止影响下一次判断 //因为i在变化，所以每一次的tmp插入的string是不一样的 tmp.clear(); } //最后返回这个vector<int> v即可 return v; } };
