手写算法：串联所有单词的子串

30. 串联所有单词的子串

注意题目：words 数组是由一些长度相同的单词组成，且连接的时候中间不能有其他字符，但是顺序可以不用考虑。

那么这样的话：

1. 通过拿到 words 数组的长度，乘以每个单词的长度，这样能得出整个串联的字符串的长度

2. 记录当前单词出现的次数，跟串联的字符串相比较，每次以一个单词为单位，依次比较，出现相同的数量-1

3. 当次数变为 0 的时候，那么就是全部匹配上了

function findSubstring(s, words) {
  // 单个单词的字符串长度
  const wordLen = words[0].length;
  // words的数组长度
  const wordsSize = words.length;
  // 整个words数组串联在一起字符串的长度
  const totalCharLen = wordLen * wordsSize;

  // 记录关键单词出现的次数
  let wordsCount = {};
  words.forEach(w => (wordsCount[w] = (wordsCount[w] || 0) + 1));

  let result = [];

  for (let i = 0; i <= s.length - totalCharLen; i++) {
    // 每次循环都要重新比较字符串是否相对应
    let tempCount = { ...wordsCount };
    let count = wordsSize;

    // 每次比较一个单词，依次比较
    for (let j = i; j < i + totalCharLen; j += wordLen) {
      // 复制截取分割，每个单词为一组
      const w = s.slice(j, j + wordLen);
      // 如果tempCount没有此单词，或者之前已经对比过了，不存在此单词，现在对比的时还有此单词，说明不匹配。直接跳过
      if (!(w in tempCount) || tempCount[w] <= 0) break;

      // 否则的话，减去对应的数量
      tempCount[w]--;
      count--;
    }
    // 当数量为0时，说明都匹配完成，把当前字符的索引推入result
    if (count === 0) result.push(i);
  }
  return result;
}

参考答案