原题：串联所有单词的子串

思路：滑动窗口

思路

这题其实很容器就能想到用哈希表 + 滑动窗口来解决，但是很多人会被字符串中与子串单词不同长度的单词拦下

其实并不用考虑如何跳过不同长度的单词，我们只要把每一个字符都遍历过就 ok

例如我们有一个字符串 "fofoobarfoo"，单词列表 ["foo", "bar"]单词长度为 wordLen = 3，我们只需要处理从下标 0 到 wordLen - 1 开始遍历的情况即可，下面枚举下遍历过程。

遍历过程

每次遍历下标步数取单词长度 wordLen 即 3

第一次 i = 0 有以下结果组合: "fofoob", "oobarf"

第二次 i = 1 : "ofooba", "obarfo"

第三次 i = 2 : "foobar", "barfoo"

遍历的所有组合中已经包含了所有结果，不需要考虑中间遇到的长度不相等的单词

思路简述

1. 设计一个哈希表来确定当前的子串是合法的

题目要求不能有其它单词、单词出现次数必须一致、任意排序，从而可以很快想到用单词哈希表记录其出现次数即可 const map = { "wordA": 1, "wordB": 2, ... }

2. 接着就是一些基础变量的初始化

单个单词长度 wordLen
子串长度 wordTotalLen
结果 result

3. 遍历字符串

前面说到的，需要遍历几种不同的情况

1
2
3
for (let i = 0; i < wordLen; i++) {
  ...
}

4. 滑动窗口

以当前下标为起点开始滑动窗口 left = right = i
变量 count 记录单词出现的总次数
变量 tmpMap 记录当前子串的单词出现次数

开始一个循环，不停的移动窗口右侧，每次移动 wordLen 长度直到剩余字符不满足一个单词的长度 right + wordLen <= s.length

在循环体内每次移动完窗口右侧后 right += wordLen，获得最新拿到的单词

判断单词是否存在，若不存在则清空 tmpMap 和 count，窗口左侧移动到当前窗口右侧 left = right

若存在则在临时哈希表中记录次数并记录总次数 tmpMap[word]++, count++

记录完后若当前单词出现字数超过合法次数，则移动窗口左侧到当前单词左侧，即舍弃掉前面的结果

最后经过上面去重后，如果当前计数等于单词数，则当前窗口内的为合法结果

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  // 单个单词长度
  const wordLen = words[0].length;
  // 子串长度
  const wordTotalLen = wordLen * words.length;
  // 如果子串大于字符串，返回空
  if (wordTotalLen > s.length) return [];
  // 存放结果
  const result = [];
  // 记录子串单词次数的哈希表
  const map = {};
  // 初始化子串出现次数
  for (let i = 0; i < words.length; i++) {
    map[words[i]] ? map[words[i]]++ : (map[words[i]] = 1);
  }
  /**
   * 每次我们都以单词长度为一步
   * 但字符串中会有长度不为单词长度的词
   * 所以我们需要遍历到每一个下标，即从下标 0 到单词长度 wordLen 开始遍历的情况
   */
  for (let i = 0; i < wordLen; i++) {
    // 窗口左侧
    let left = i;
    // 窗口右侧
    let right = i;
    // 子串单词总次数
    let count = 0;
    // 临时计算当前窗口子串次数的哈希表
    let tmpMap = {};
    // 保证右窗口不越界
    while (right + wordLen <= s.length) {
      // 截取当前窗口右侧的下一个单词
      const word = s.substring(right, right + wordLen);
      // 滑动右侧窗口
      right += wordLen;
      // 如果单词不在子串哈希表中，从窗口最右侧开始重新寻找
      if (!map[word]) {
        left = right;
        tmpMap = {};
        count = 0;
      } else {
        // 当前单词出现次数 +1
        tmpMap[word] ? tmpMap[word]++ : (tmpMap[word] = 1);
        // 单词总出现次数 +1
        count++;
        /**
         * 判断当前单词是否超出出现次数
         * 是的话会进入循环
         * 把窗口中当前单词左侧所有单词删除，并把窗口左侧移动到当前单词起点
         */
        while (tmpMap[word] > map[word]) {
          // 需要删除的单词
          const delWord = s.substring(left, left + wordLen);
          // 删除单词计数
          tmpMap[delWord]--;
          // 删除计数
          count--;
          // 滑动窗口左侧
          left += wordLen;
        }
        // 经过前面的去重后，如果当前单词计数 === 子串单词总数，则当前窗口的子串为结果，记录当前窗口左侧下标
        if (count == words.length) result.push(left);
      }
    }
  }
  return result;
};