LeetCode.30 - 串联所有单词的子串

• LeetCode - 30. 串联所有单词的子串

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

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

• 例如，如果 words = [“ab”,”cd”,”ef”]， 那么 “abcdef”， “abefcd”，”cdabef”， “cdefab”，”efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

思路

1. 将 s 进行分段，每段长度为 words 的长度；而后采用滑动窗口的方式进行检查

var findSubstring = function (s, words) {
  const wordLength = words[0].length
  const matchLength = wordLength * words.length
  const wordsCount = {}
  for (const item of words) {
    if (!wordsCount[item]) {
      wordsCount[item] = 0
    }
    ++wordsCount[item]
  }
  const result = []
  for (let startIndex = 0; startIndex < wordLength; ++startIndex) {
    let checkMap = { ...wordsCount }
    let left = startIndex
    let right = startIndex
    while (right + wordLength <= s.length) {
      const curWord = s.substring(right, right + wordLength)
      right += wordLength
      if (checkMap[curWord] === undefined) {
        checkMap = { ...wordsCount }
        left = right
        continue
      }
      if (checkMap[curWord] === 0) {
        while (s.substring(left, left + wordLength) !== curWord) {
          left += wordLength
        }
        left += wordLength
        right = left
        checkMap = { ...wordsCount }
        continue
      }
      --checkMap[curWord]
      if (right - left === matchLength) {
        result.push(left)
        ++checkMap[s.substring(left, left + wordLength)]
        left += wordLength
      }
    }
  }
  return result
}