串联所有单词的子串

力扣🔗：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words (opens new window)

题目

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

解题思路

• 依次遍历字符串 s，每次循环由当前索引 i 作为起始位置，向后截取所有单词组成的字符串长度的子串（下面的代码实现是依次向后截取每个单词长度的子串，一共截取 words.length 次），判断该子串中的每个单词出现次数是否与 words 中出现次数相同。
• 解题的关键点是通过创建一个 map 对象，以保存每个单词出现的次数，很方便地解决了如何判断截取的子串是不是所有单词组成的所有子串的其中之一。

代码实现

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
function findSubstring(s, words) {
  if (words.length === 0) return []

  const wordLen = words[0].length // 每个单词长度
  const strLength = words.length * wordLen // 所有单词拼接成的字符串总长度
  const map = words.reduce((p, c) => { 
    // 存储每个单词出现的次数，key 为单词，value 为次数
    p[c] = (p[c] || 0) + 1
    return p
  }, {})
  const res = []

  for (let i = 0; i < s.length - strLength + 1; i++) {
    // 依次遍历 s 中的字符
    // 每次选取由当前字符作为起始位置，长度为所有单词组成的字符串总长所组成的子串
    // 判断该子串中出现的单词次数是否与 tempMap 中每个单词出现次数匹配

    const tempMap = { ...map }
    let rest = words.length // 需要匹配的剩余单词数
    let start = i
    while (rest > 0) {
      const word = s.substr(start, wordLen) // 截取单词
      if (!(word in tempMap) || tempMap[word] === 0) break // 如果单词不存在或该单词已经完成匹配

      tempMap[word]--
      rest--
      start += wordLen
    }

    rest === 0 && res.push(i) // 全部匹配，插入起始位置
  }

  return res
}