面试经典题---30.串联所有单词的子串

30.串联所有单词的子串

我的解法：

滑动窗口：

• 解法中用到了两个哈希表map1和map2，分别用于记录words中各个单词的出现频数和当前滑动窗口[left, right)中单词的出现频数；
• 外部for循环i从0到len - 1，内部while循环每次会让滑动窗口滑动len步，即开头位置为i时，这一轮就可以遍历到i + k*len开头的子串，因此i取0到len - 1可以覆盖所有的子串开头情况；
• 内部while循环每次先取right开头的长度为len的子串tmp，判断tmp是否是words中的单词：
  • 不是则更新窗口左端点，清空count和哈希表map2
  • 属于words中的单词时count加1，更新哈希表map2，若tmp重复出现了，则要收缩滑动窗口左端，并更新count和map2（注意判断重复出现这里用的是while循环）

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> res;if(s.empty() || words.empty()){return res;}int len = words[0].size();int size = words.size();unordered_map<string, int> map1;for(auto w : words){map1[w]++;}for(int i = 0; i < len; ++i){int left = i, right = i;int count = 0;unordered_map<string,int> map2;while(right + len <= s.size()){string tmp = s.substr(right, len);right += len;if(map1.count(tmp) == 0){left = right;count = 0;map2.clear();}else{count++;map2[tmp]++;while(map1[tmp] < map2[tmp]){string re_word = s.substr(left, len);count--;map2[re_word]--;left += len;}if(count == size){res.push_back(left);}}}}return res;}
};