题目内容

给定一个字符串 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”]
输出：[]

题解

本题是一个采用滑动窗口算法求解的题目。针对本题，有如下的思考过程：

1、单词的长度相同，因此方便我们能够简化对字符串遍历的方式。具体如下图：

由于单词的长度全部一致，遍历时的起始位置直接按照w来划分。这样做的好处就是，如果存在符合题目要求的匹配，那么每个单词一定会恰好卡在我们划分的某一种情况中。

2、在上述分隔的情况下，问题可以转化为在给定的分隔情况下，找到其中符合题目的要求的连续的段的开始下标，然后重复上述操作，直到全部遍历完成即可。

3、在具体的算法操作中，为方便后续的操作，可以将给定的m(words.size())个单词存入hash表中，假设为tot。然后维护一个长度为m的滑动窗口，将滑动窗口中的元素也维护到hash表中，假设为wd。每次窗口向前移动时，删除最左边的旧元素，最右边增加一个新元素。

4、这里，我们用一个变量cnt维护wd中有多少个单词在给定的tot集合中出现过。具体来说两层含义：wd中如果出现tot中没有的单词，则cnt不会统计此单词数目；wd中出现tot中存在的单词，但其数量超过tot中出现的数量，则cnt不会计算超过的部分的单词数量。

5、在维护好cnt之后，可以直接使用cnt == tot.size()进行判断，如果一致，则认为发现了符合题目条件的连续部分，答案中记录对应起始位置；不一致则窗口继续滑动，直到结束。

具体，请看代码注释。

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if (words.empty()) return res;//判空
        int n = s.size(), m = words.size(), w = words[0].size();//n为字符串长度，m为单词的数量，w为单词的长度
        unordered_map<string, int> tot;//定义给定的单词的hash表
        for (auto& word : words) tot[word] ++ ;//枚举一下全部单词，相当于将单词映射到了tot这个hash表中
				
      	//
        for (int i = 0; i < w; i ++ ) {
            unordered_map<string, int> wd;//定义每一组中的hash表，为滑动窗口服务。
            int cnt = 0;
          	//枚举情况
            for (int j = i; j + w <= n; j += w) {
              	//枚举的长度要在字符串的长度以内，因此j+w <=n
              	//每次间隔长度为w，因此j += w
                if (j >= i + m * w) {
                  	//j代表的是从0到j的总长度，这里是判断窗口是否达到了最大，即m*w,i要加上是因为用总体长度和j判断才一致。
                  	//在滑动窗口的大小达到最大时，要对左边的单词删除，对右边的单词增加。这里取出窗口最左边的单词
                    auto word = s.substr(j - m * w, w);
                  	//将hash表中对应的部分--
                    wd[word] -- ;
                  	//如果wd对应单词数量减掉后，小于了tot中的对应单词的数量，说明减去了一个有效的单词，cnt需要--
                    if (wd[word] < tot[word]) cnt -- ;
                }
              	//找出右边新添加的单词
                auto word = s.substr(j, w);
              	//对wd添加映射
                wd[word] ++ ;
              	//同理，如果为有效单词，则cnt++
                if (wd[word] <= tot[word]) cnt ++ ;
              	//判断是否cnt等于单词数量，满足则计算当前连续区间的起始位置，放入答案中。
                if (cnt == m) res.push_back(j - (m - 1) * w);
            }
        }

        return res;
    }
};