30.串联所有单词的子串

串联所有单词的子串

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

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

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

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,”bar”]
输出：[0,9]

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
输出：[]

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
输出：[6,9,12]

提示：

• 1 <= s.length <= $10^4$
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30

解析

因为 words 中所有单词长度相同，可以利用滑动窗口，以单词长度为步长滑动。

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

  const wordLen = words[0].length;
  const wordCount = words.length;
  const totalLen = wordLen * wordCount;
  const result = [];

  // 统计 words 中每个单词的出现次数
  const wordMap = {};
  for (const word of words) {
    wordMap[word] = (wordMap[word] || 0) + 1;
  }

  for (let i = 0; i <= s.length - totalLen; i++) {
    const seen = {};
    let j = 0;
    while (j < wordCount) {
      const word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
      if (!wordMap[word]) break;
      seen[word] = (seen[word] || 0) + 1;
      if (seen[word] > wordMap[word]) break;
      j++;
    }
    if (j === wordCount) result.push(i);
  }
  return result;
};

对每个起始位置，依次截取等长单词并与目标单词集合比较。时间复杂度 O(n * m * k)，其中 n 为字符串长度，m 为单词个数，k 为单词长度。