30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。
s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

示例 1：
输入：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] 也是可以的。

示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：
输入：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"] 顺序排列的连接。

提示：
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words

javascript

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
  const wordsLen = words.length
  const wordLen = words[0].length
  const totalLen = wordsLen * wordLen
  if (s.length < totalLen) return []
  const res = [], wordsMap = new Map()

  for (let i = 0; i < wordsLen; i++) {
    const ele = words[i]
    wordsMap.set(ele, (wordsMap.get(ele) || 0) + 1)
  }

  for (let i = 0; i <= s.length - totalLen; i++) {
    const subStr = s.slice(i, i + totalLen)
    const subStrMap = new Map()
    let flag = true
    for (let j = 0; j < subStr.length; j += wordLen) {
      const ele = subStr.slice(j, j + wordLen)
      subStrMap.set(ele, (subStrMap.get(ele) || 0) + 1)
      if (subStrMap.get(ele) > wordsMap.get(ele) || !wordsMap.has(ele)) {
        flag = false
        break
      }
    }
    if (flag) {
      res.push(i)
    }
  }

  return res
}

var findSubstring = function (s, words) {
  const sLen = s.length, wordsLen = words.length, wordLen = words[0].length, totalLen = wordsLen * wordLen, res = []

  for (let i = 0; i < wordLen; i++) {
    if (i + totalLen > sLen) break

    const map = new Map()

    for (let j = 0; j < wordsLen; j++) {
      const word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
      map.set(word, (map.get(word) || 0) + 1)
    }

    for (let j = 0; j < wordsLen; j++) {
      const word = words[j]
      map.set(word, (map.get(word) || 0) - 1)
      if (map.get(word) == 0) {
        map.delete(word)
      }
    }

    for (let start = i; start <= sLen - totalLen; start += wordLen) {
      if (start != i) {
        let word = s.substring(start + (wordsLen - 1) * wordLen, start + totalLen)
        map.set(word, (map.get(word) || 0) + 1)
        if (map.get(word) == 0) {
          map.delete(word)
        }

        word = s.substring(start - wordLen, start)
        map.set(word, (map.get(word) || 0) - 1)
        if (map.get(word) == 0) {
          map.delete(word)
        }
      }
      if (map.size == 0) {
        res.push(start)
      }
    }
  }
  return res
}

console.log(findSubstring('foobarthe', ['foo', 'bar']))
console.log(findSubstring('barfoothefoobarman', ['foo', 'bar']))
console.log(findSubstring('wordgoodgoodgoodbestword', ['word', 'good', 'best', 'word']))
console.log(findSubstring('barfoofoobarthefoobarman', ['bar', 'foo', 'the']))

30. 串联所有单词的子串 #

30. 串联所有单词的子串