力扣题解：30.串联所有单词的子串（困难）

前言

这道题难度较大，涉及的东西比较多，值得一做，如果没有算法基础不建议尝试，应该先从简单的做起。题解采用C++，涉及到STL中的map和pair数据结构。由于没有官方题解，本题解可能还有优化空间。
题解讲的比较详细，一步步来建立整个算法，保姆级教程，希望你能耐心一步步看完。
该题涉及：

• 滑动窗口（双指针）
• 哈希表
• 字符串

题目

给定一个字符串 s 和一些长度相同的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

提示：

• 1 <= s.length <= 10^4
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

题解

本题采用滑动窗口的思想，可能有些同学想不到，先讲一下为什么采用滑动窗口。

我们先从最朴素的想法开始，我们将wordLength * words.size()长度内的字符串（words中所有单词拼出来的长度），每wordLength个字符处理成一个单词，然后依次计数，对照words中单词的计数。

• 如果字符串中拆出来的单词不在words中，那么肯定匹配失败，我们遍历下一个
• 如果单词计数不满足words中的计数（多于或少于），那么也肯定匹配失败，我们遍历下一个
• 当单词计数恰好等于words中的计数时，我们才算找到一个答案，但因为我们需要找到所有匹配的下标，我们仍然遍历下一个

在这过程中，会产生重复的计算，我们想象这样一个场景：箭头为匹配的起点
在字符串分割出的单词中，在中后段有一个不属于words，但我们每次遍历到那时，才发现失配，于是继续下一趟遍历，又失配，直到跳过了这个单词。那为什么不发现失配之后就直接跳到失配的单词后面呢？

于是我们有了一个最直观的思考，逐步想到滑动窗口。

我们再从头开始，考虑一个数据结构用来对单词进行计数，我们采用这样一个数据结构来记录words中每个单词的个数。

map<string, pair<int, int>> record

有些同学不了解C++中的数据结构，简单介绍下。
其中map为哈希表，pair<int, int>为一个二元组。我们用pair的第一个值first来记录当前单词的计数，用第二个值second来记录words中出现的次数，即可以达到的最大值。

所以，我们先计算出record的值：

map<string, pair<int, int>> record;
for(int i = 0; i < words.size(); ++i){
	if(record.find(words[i]) == record.end()){
		record[words[i]] = pair<int, int>({0, 1});
	}else{
		record[words[i]].second++;
	}
}

于是，我们可以得到一系列的二元组，例如：

输入：["word", "word", "good", "best"]
输出(record)：
["word"]:{0, 2}
["good"]:{0, 1}
["best"]:{0, 1}

接着，我们继续考虑如何进行匹配，仍然从最朴素的想法开始，因为要匹配单词，所以肯定有一个循环，迭代步数是wordLength，这样才将字符串拆成单词。
但有特殊情况，如"aword"，我们要匹配word，如果只有迭代步数为wordLength的遍历，我们只能得到awor，所以我们还需要一个迭代步数为1的循环，才能让拆分从w开始，拆出word。
这里需要注意一点，如果对"getsetletput"进行拆分，从g开始和从s开始，在后续的遍历中会有重复。例如从g开始拆分出["get", "set", "let", "put"]，从s开始拆分出["set", "let", "put"]，实际上单词内容是一样的。所以我们迭代步数为1的循环，最多迭代wordLength次。

所以，我们有了一个大框架：

for(int i = 0; i < wordLength; ++i){
	int j = ...;
	while(...){
		j += wordLength;
	}
}

接着我们思考滑动窗口如何操作，即最内层的循环。我们有以下几条规则：其中word为right至right + wordLength的字符组成的单词。

• 起始left = right = i，优先移动right扩大窗口
• 移动right的情况：
  • 如果单词word在words中，那么我们让right += wordLength，且使record[word].first++。需要满足条件record[word].first < record[word].second，即加入后不会超过单词计数的最大值。
  • 如果单词word不在words中，或当前计数已经达到最大值，那么就说明发生了失配，需要移动left，我们在下面进行说明如何移动。
• 移动left的情况：
  • 如果移动right之后能够满足right - left == wordLength * words.size()，则说明找到一个匹配的下标left，我们移动left继续寻找下一个。left += wordLength。
  • 如果word不在words中，说明我们可以直接跳到该单词的后面开始匹配，则right = left = right + wordLength。
  • 如果word在words中，但当前计数已经达到最大值，那么我们要移动left，直到加入word后不再会超过最大计数值。这样子我们才能继续移动right，否则一移动right就产生非法情况。

上述过程要注意数组越界和边界条件，因为文字表述比较长，可能短时间不容易理解，建议大家实际动手模拟一下算法过程，或者在调试中实际运行一下，看下代码执行过程是怎么样的，帮助理解。

接下来我们就可以开始完成我们的算法了！

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if(s.size() < words[0].size()) return result;

        //题目保证words中有元素
        int wordLength = words[0].size();
        int dist = wordLength * words.size();

        map<string, pair<int, int>> record;
        for(int i = 0; i < words.size(); ++i){
            if(record.find(words[i]) == record.end()){
                //如果record中没有元素，初始化一个
                record[words[i]] = pair<int, int>({0, 1});
            }else{
                record[words[i]].second++;
            }
        }

        for(int i = 0; i < wordLength; ++i){
            int left = i, right = i;
            while(right <= s.size() - wordLength){
                string word(s, right, wordLength);
                if(record.find(word) != record.end()){
                    //如果单词在words中
                    if(record[word].first < record[word].second){
                        right += wordLength;
                        ++record[word].first;
                    }else{
                        //右移left，使窗口内单词计数满足条件
                        while(record[word].first >= record[word].second){
                            string temp(s, left, wordLength);
                            --record[temp].first;
                            left += wordLength;
                        }
                    }
                }else{
                    //如果单词不在words中，直接移动left且清空计数
                    right = left = right + wordLength;
                    for(auto& count : record){
                        count.second.first = 0;
                    }
                }
                if(right - left == dist){
                    //窗口长度满足条件，即找到个匹配的下标left
                    result.push_back(left);
                    string temp(s, left, wordLength);
                    --record[temp].first;
                    left += wordLength;
                }
            }
            //每次迭代都要清空计数
            for(auto& count : record){
                count.second.first = 0;
            }
        }
        return result;
    }
};

可能有些不了解C++的同学会对清空计数中的count.second.first = 0感到疑惑。STL中的map实际上就是用pair实现的，即map储存的是pair<type1, type2>这样的键值对，type1是下标，type2是值。所以遍历map实际上拿到的是这样的键值对。

count.second.first = 0
//等价于
pair<int, int> temp = count.second;
int num = temp.first;

题解分析：

• 时间复杂度：$O(m*n)$，其中m为字符串长度，n为单词长度
• 空间复杂度：$O(n)$，n为单词个数

---