Skip to main content

串联所有单词的子串

题目​

给定一个字符串 s 和一个字符串数组 words. words 中所有字符串长度相同.

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串.

例如, 如果 words = ["ab", "cd", "ef"], 那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", "efcdab" 都是串联子串. "acdbef" 不是串联子串, 因为他不是任何 words 排列的连接. 返回所有串联字串在 s 中的开始索引. 你可以以任意顺序返回答案.

提示:
  • 1 <= s.length <= 10⁴
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] 和 s 由小写英文字母组成
示例
输入: s = "barfoothefoobarman", words = ["foo", "bar"]
输出: [0, 9]
解释: 因为 words.length == 2 同时 words[i].length == 3, 连接的子字符串的长度必须为 6.
子串 "barfoo" 开始位置是 0. 它是 words 中以 ["bar", "foo"] 顺序排列的连接.
子串 "foobar" 开始位置是 9. 它是 words 中以 ["foo", "bar"] 顺序排列的连接.
输出顺序无关紧要. 返回 [9,0] 也是可以的.
输入: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]
输出: []
解释: 因为 words.length == 4 并且 words[i].length == 4, 所以串联子串的长度必须为 16.
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接.
所以我们返回一个空数组.
输入: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]
输出: [6, 9, 12]
解释: 因为 words.length == 3 并且 words[i].length == 3, 所以串联子串的长度必须为 9.
子串 "foobarthe" 开始位置是 6. 它是 words 中以 ["foo", "bar", "the"] 顺序排列的连接.
子串 "barthefoo" 开始位置是 9. 它是 words 中以 ["bar", "the", "foo"] 顺序排列的连接.
子串 "thefoobar" 开始位置是 12. 它是 words 中以 ["the", "foo", "bar"] 顺序排列的连接.

题解​

朴素解法的思路是先把 words 中的每个 word 放到哈希表 map 中, 值是其出现的数量. 然后从头遍历 s, 截取 s.slice(i, i + n * w) 子字符串记为 subStr, 把 subStr 按照 word 的长度切割, 把每一份的子字符串存到一个新的哈希表 subMap 中, 和 map 一样, 值是其出现的数量. 最后比较 subMap 和 map, 如果相等, 说明 words 的某个组合 使一个合法的串联子串..

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  const m = s.length
  const n = words.length
  const w = words[0].length

  //  把 words 中的元素存储到哈希表中
  const map = new Map()
  for (const word of words) {
    map.set(word, map.has(word) ? map.get(word) + 1 : 1)
  }

  const res = []
  for (let i = 0; i < m; i++) {
    // 因为 words 中的每个子元素长度相等, 因此串联子串的长度是 n * w
    const end = i + n * w

    // 注意如果右边界超过 m 要终止循环
    if (end > m) break

    // 因此字符串切片就是 s.slice(i, i + n * w)
    const subStr = s.slice(i, end)

    // 声明一个新的哈希表 subMap, 记录 subStr 中每 w 个小字符串
    const subMap = new Map()
    for (let j = 0; j < n * w; j += w) {
      const sub = subStr.slice(j, j + w)

      // 如果 words 中都没有子字符串, 可以提前终止
      if (!words.includes(sub)) break

      subMap.set(sub, subMap.has(sub) ? subMap.get(sub) + 1 : 1)
    }

    // 计算两个哈希表是否相同, JavaScript 没有直接的方法, 得手撕一个
    // Rust 直接判断 map == sub_map 即可
    if (isEqual(map, subMap)) {
      res.push(i)
    }
  }

  return res
}

/**
 * @param {Map} map1
 * @param {Map} map2
 * @return {boolean}
 */
var isEqual = function (map1, map2) {
  for (const key of map1.keys()) {
    if (map1.get(key) !== map2.get(key)) return false
  }

  return true
}