困难

问题描述

给定一个字符串 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 <= 104
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

朴素哈希表

使用哈希表 $map$ 记录 $words$ 中各单词出现的次数，记 $m$ 为单词个数，$w$ 为单个单词的长度，需要查找的字符串长度即为 $m \times w$。枚举字符串 $s$ 中长度为 $m \times w$ 的子字符串 $str$，使用另外一个哈希表 $cur$ 统计子字符串 $str$ 长度为 $w$ 的单词，再与哈希表 $map$ 中记录作对比，若相同，则记录枚举的下标值。

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  const map = new Map()
  const w = words[0].length
  const m = w * words.length
  for (const word of words) {
    map.set(word, (map.get(word) || 0) + 1)
  }
  const ans = []
  for (let i = 0; i <= s.length - m; i++) {
    const cur = new Map()
    const str = s.substr(i, m)
    for (let j = 0; j < str.length; j += w) {
      const sub = str.substr(j, w)
      cur.set(sub, (cur.get(sub) || 0) + 1)
    }
    let match = true
    for (const key of map.keys()) {
      if (map.get(key) !== cur.get(key)) {
        match = false
        break
      }
    }
    if (match) ans.push(i)
  }
  return ans
}

• 时间复杂度：$O(n \times m)$，$n$ 为字符串 $s$ 的长度，$m$ 为单词数组长度。
• 空间复杂度：$O(m \times w)$，$m$ 为单词数组长度，$w$ 为单个单词长度。

滑动窗口

同样使用哈希表 $map$ 记录 $words$ 中各单词出现的次数，记 $m$ 为单词个数，$w$ 为单个单词的长度，建立一个 $m \times w$ 的滑动窗口，滑动窗口中按照长度 $w$ 划分成 $m$ 的单词，每个单词个数都记录到哈希表 $cur$ 中，当 $map$ 与 $cur$ 中记录相同时，说明窗口中的字符串是满足要求的，记录窗口的首字母下标，之后窗口滑动单个单词长度的距离，移出滑动窗口的单词在 $cur$ 中记录减一，移入滑动窗口的单词在 $cur$ 中记录加一，再次进行比较。这样只需按单个单词长度范围内偏移量进行分类枚举，就能减少大量重复搜索。

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  const map = new Map()
  const n = s.length
  const w = words[0].length
  const m = words.length
  for (const word of words) {
    map.set(word, (map.get(word) || 0) + 1)
  }
  const ans = []
  for (let i = 0; i < w; i++) {
    const cur = new Map()
    let cnt = 0
    for (let j = i; j + w <= n; j += w) {
      const word = s.substr(j, w)
      if (cnt === m) {
        const prev = s.substr(j - w * m, w)
        if (cur.get(prev) === 1) cur.delete(prev)
        else cur.set(prev, cur.get(prev) - 1)
        cnt--
      }
      cur.set(word, (cur.get(word) || 0) + 1)
      cnt++
      if (cnt === m) {
        let match = true
        for (const key of map.keys()) {
          if (map.get(key) !== cur.get(key)) {
            match = false
            break
          }
        }
        if (match) ans.push(j - (m - 1) * w)
      }
    }
  }
  return ans
}

• 时间复杂度：$O(n \times w)$，$n$ 为字符串 $s$ 的长度，$w$ 为单个单词长度。
• 空间复杂度：$O(m \times w)$，$m$ 为单词数组长度，$w$ 为单个单词长度。