见注释。滑动窗口还是好用。
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int>res; if(words.empty()||s.empty()) return res; map<string,int>allWords; int wordLen=words[0].size(); int wordNum=words.size(); for(int i=0;i<wordNum;i++) { if(allWords.find(words[i])!=allWords.end()) allWords[words[i]]++; else allWords.insert(make_pair(words[i],1)); } bool hasRemoved=false; map<string, int> hasWords; //将所有移动分成 wordLen 类情况 即从i=0,1,2...wordLen-1处开始,每次移动WordLen长度 for (int j = 0; j < wordLen; j++) { hasWords.clear(); int num = 0; //记录当前hasWords中有多少个单词 for (int i = j; i +wordNum * wordLen< s.length()+1; i = i + wordLen) { //每次判断一个窗口,窗口从i开始长 wordNum * wordLen 窗口每次移动一个单词长度 hasRemoved = false; //防止情况三移除后,情况一继续移除 while (num < wordNum) { string word = s.substr(i + num * wordLen,wordLen); if (allWords.find(word)!=allWords.end()) { if(hasWords.find(word)!=hasWords.end()) hasWords[word]++; else hasWords.insert(make_pair(word,1)); //遇到了符合的单词,但是次数超了 if (hasWords[word] > allWords[word]) { hasRemoved = true; int removeNum = 0; //一直移除单词,直到次数符合了 while (hasWords[word] > allWords[word]) { string firstWord = s.substr(i + removeNum * wordLen,wordLen); hasWords[firstWord]-=1; removeNum++; } num = num - removeNum + 1; //加 1 是因为我们把当前单词加入到了 HashMap 2 中 i = i + (removeNum - 1) * wordLen; //这里依旧是考虑到了最外层的 for 循环,看情况二的解释 break; } //出现情况二,遇到了不匹配的单词,直接将 i 移动到该单词的后边(但其实这里 //只是移动到了出现问题单词的地方,因为最外层有 for 循环, i 还会移动一个单词 //然后刚好就移动到了单词后边) } else { hasWords.clear(); i = i + num * wordLen; num = 0; break; } num++; } if (num == wordNum) { res.push_back(i); } //出现情况一,子串完全匹配,我们将上一个子串的第一个单词从 HashMap2 中移除 if (num > 0 && !hasRemoved) { string firstWord = s.substr(i,wordLen); hasWords[firstWord]-=1; num = num - 1; } } } return res; } };