哈希算法题目：串联所有单词的子串
字数 3018 2025-12-09 08:22:09

哈希算法题目：串联所有单词的子串

题目描述

给定一个字符串 s 和一个字符串数组 words，words 中所有字符串的长度相同。
题目要求你找出 s 中所有可以由 words 中所有字符串按任意顺序串联形成的子串的起始索引。
注意：words 中可能有重复的单词，因此需要保证子串中每个单词的出现次数与 words 中的出现次数完全匹配。

示例 1
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：从索引 0 开始的子串 "barfoo" 是 "bar" 和 "foo" 的串联，从索引 9 开始的子串 "foobar" 是 "foo" 和 "bar" 的串联。

示例 2
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：虽然 "wordgoodgoodgoodbestword" 包含了这些单词，但无法按 words 中出现的次数（"word" 出现两次，实际子串中只有一次）完全匹配。

解题思路

这个问题本质上是固定长度单词的多模式匹配。
核心思路：

  1. 已知每个单词长度相同，设为 wordLen，单词个数为 numWords，那么目标子串的长度固定为 totalLen = wordLen * numWords。
  2. 在 s 中，从每个可能的起始位置开始，依次截取 totalLen 长度的子串，然后检查这个子串是否能拆分成 words 中所有单词的某种排列。
  3. 检查时，需要统计子串中每 wordLen 长度的片段的出现次数，并与 words 的词频表进行比对。

暴力法：对每个起始位置，截取子串并拆分，用哈希表统计词频，与 words 的词频表比较。时间复杂度约为 O(n * totalLen)，在 n 较大时可能超时。

优化方向：利用滑动窗口思想，但这里的“窗口”移动步长不是字符，而是单词长度。我们需要考虑以 0, 1, 2, ..., wordLen-1 为起始偏移，分别进行滑动窗口扫描，这样可以将时间复杂度降为 O(wordLen * n / wordLen) ≈ O(n)。

详细解题步骤

假设：

  • n = len(s)
  • numWords = len(words)
  • wordLen = len(words[0])
  • totalLen = numWords * wordLen

步骤 1：构建目标词频哈希表
首先，统计 words 中每个单词应出现的次数，存入哈希表 wordCount 中。
示例 1 中：wordCount = {"foo":1, "bar":1}

步骤 2：外层循环遍历起始偏移
因为单词长度固定，我们可以分别从 s 的下标 0, 1, 2, ..., wordLen-1 开始，作为滑动窗口的起始位置。
原因：滑动窗口每次移动一个单词长度，如果我们只从 0 开始，可能会错过以 1,2,... 开头但恰好能匹配的子串。

例如：s = "abfoobar", words = ["foo","bar"]，单词长度为 3，如果只从 0 开始，得到 "abf" 无效，但从 1 开始可以得到 "bfo" 等，但实际匹配是从 3 开始。而如果我们从偏移 1 开始扫描，就能捕捉到。

步骤 3：对每个起始偏移进行滑动窗口扫描
初始化：

  • 当前窗口的起始指针 left，当前检查位置指针 right（以单词为单位移动，实际索引需乘 wordLen）。
  • 哈希表 windowCount 记录当前窗口中每个单词的出现次数。
  • 计数器 count 表示当前窗口中已匹配的单词数（指出现次数不超过 wordCount 中次数的单词）。

过程：

  1. 从 right 开始，每次取一个单词 word = s[right: right+wordLen]。
  2. 如果 word 不在 wordCount 中，说明当前窗口无效，直接将窗口重置到 right+wordLen 处，清空 windowCount 和 count。
  3. 如果 word 在 wordCount 中：
    • 将 windowCount[word] 加 1。
    • 如果 windowCount[word] <= wordCount[word]，则 count 加 1，否则说明这个单词在窗口中多出现了，需要移动 left 缩小窗口直到这个单词不多余。
  4. 当 count == numWords 时，说明窗口中的单词正好匹配 words，记录当前 left 作为答案之一。
  5. 窗口滑动：每次 right 增加 wordLen，如果窗口长度（单词数）超过 numWords，则需要移动 left 并更新 windowCount 和 count。

步骤 4：收集结果
将每个起始偏移下找到的起始索引加入结果列表，注意可能重复（但题目要求唯一结果，可用集合去重或直接保证不重复添加）。

举例说明

以 s = "barfoothefoobarman", words = ["foo","bar"] 为例：

  • wordLen = 3, numWords = 2, totalLen = 6
  • wordCount = {"foo":1, "bar":1}

起始偏移 0：
窗口滑动过程：

  1. left=0, right=0，单词 "bar" 在 wordCount 中，windowCount={"bar":1}, count=1。
  2. right=3，单词 "foo" 在表中，windowCount={"bar":1,"foo":1}, count=2，找到匹配，记录 left=0。
  3. 窗口右移，left=3, right=6，单词 "the" 不在表中，重置窗口，left=9，继续扫描...
  4. 最终在 left=9 找到第二个匹配。

起始偏移 1 和 2 也会扫描，但本例中没有额外匹配。

结果：[0,9]

关键点总结

  1. 因为单词长度相同，可以将问题转化为固定长度片段的多模式匹配。
  2. 滑动窗口时，以单词长度为单位移动，但需要从不同的字符偏移开始，确保不遗漏。
  3. 用两个哈希表分别记录目标词频和窗口词频，通过计数器判断窗口是否匹配。
  4. 时间复杂度：外层循环 wordLen 次，内层滑动窗口线性扫描，总体 O(wordLen * (n/wordLen)) = O(n)。
  5. 空间复杂度：O(numWords * wordLen) 用于存储哈希表。

扩展思考

  • 如果 words 中有很多重复单词，算法依然有效，因为哈希表记录的是次数。
  • 如果 s 非常长，words 很多，但 wordLen 较小，算法仍然高效。
  • 可以进一步优化：当遇到不在字典的单词时，可以直接跳过后，因为包含该单词的任何窗口都不可能匹配。
哈希算法题目：串联所有单词的子串 题目描述 给定一个字符串 s 和一个字符串数组 words ， words 中所有字符串的长度相同。 题目要求你找出 s 中所有可以由 words 中所有字符串按任意顺序串联形成的子串的起始索引。 注意： words 中可能有重复的单词，因此需要保证子串中每个单词的出现次数与 words 中的出现次数完全匹配。 示例 1 输入： s = "barfoothefoobarman" , words = ["foo","bar"] 输出： [0,9] 解释：从索引 0 开始的子串 "barfoo" 是 "bar" 和 "foo" 的串联，从索引 9 开始的子串 "foobar" 是 "foo" 和 "bar" 的串联。 示例 2 输入： s = "wordgoodgoodgoodbestword" , words = ["word","good","best","word"] 输出： [] 解释：虽然 "wordgoodgoodgoodbestword" 包含了这些单词，但无法按 words 中出现的次数（ "word" 出现两次，实际子串中只有一次）完全匹配。 解题思路 这个问题本质上是 固定长度单词的多模式匹配 。 核心思路： 已知每个单词长度相同，设为 wordLen ，单词个数为 numWords ，那么目标子串的长度固定为 totalLen = wordLen * numWords 。 在 s 中，从每个可能的起始位置开始，依次截取 totalLen 长度的子串，然后检查这个子串是否能拆分成 words 中所有单词的某种排列。 检查时，需要统计子串中每 wordLen 长度的片段的出现次数，并与 words 的词频表进行比对。 暴力法 ：对每个起始位置，截取子串并拆分，用哈希表统计词频，与 words 的词频表比较。时间复杂度约为 O(n * totalLen) ，在 n 较大时可能超时。 优化方向 ：利用 滑动窗口 思想，但这里的“窗口”移动步长不是字符，而是单词长度。我们需要考虑以 0, 1, 2, ..., wordLen-1 为起始偏移，分别进行滑动窗口扫描，这样可以将时间复杂度降为 O(wordLen * n / wordLen) ≈ O(n) 。 详细解题步骤 假设： n = len(s) numWords = len(words) wordLen = len(words[0]) totalLen = numWords * wordLen 步骤 1：构建目标词频哈希表 首先，统计 words 中每个单词应出现的次数，存入哈希表 wordCount 中。 示例 1 中： wordCount = {"foo":1, "bar":1} 步骤 2：外层循环遍历起始偏移 因为单词长度固定，我们可以分别从 s 的下标 0, 1, 2, ..., wordLen-1 开始，作为滑动窗口的起始位置。 原因：滑动窗口每次移动一个单词长度，如果我们只从 0 开始，可能会错过以 1,2,... 开头但恰好能匹配的子串。 例如： s = "abfoobar" , words = ["foo","bar"] ，单词长度为 3，如果只从 0 开始，得到 "abf" 无效，但从 1 开始可以得到 "bfo" 等，但实际匹配是从 3 开始。而如果我们从偏移 1 开始扫描，就能捕捉到。 步骤 3：对每个起始偏移进行滑动窗口扫描 初始化： 当前窗口的起始指针 left ，当前检查位置指针 right （以单词为单位移动，实际索引需乘 wordLen ）。 哈希表 windowCount 记录当前窗口中每个单词的出现次数。 计数器 count 表示当前窗口中已匹配的单词数（指出现次数不超过 wordCount 中次数的单词）。 过程： 从 right 开始，每次取一个单词 word = s[right: right+wordLen] 。 如果 word 不在 wordCount 中，说明当前窗口无效，直接将窗口重置到 right+wordLen 处，清空 windowCount 和 count 。 如果 word 在 wordCount 中： 将 windowCount[word] 加 1。 如果 windowCount[word] <= wordCount[word] ，则 count 加 1，否则说明这个单词在窗口中多出现了，需要移动 left 缩小窗口直到这个单词不多余。 当 count == numWords 时，说明窗口中的单词正好匹配 words ，记录当前 left 作为答案之一。 窗口滑动：每次 right 增加 wordLen ，如果窗口长度（单词数）超过 numWords ，则需要移动 left 并更新 windowCount 和 count 。 步骤 4：收集结果 将每个起始偏移下找到的起始索引加入结果列表，注意可能重复（但题目要求唯一结果，可用集合去重或直接保证不重复添加）。 举例说明 以 s = "barfoothefoobarman" , words = ["foo","bar"] 为例： wordLen = 3 , numWords = 2 , totalLen = 6 wordCount = {"foo":1, "bar":1} 起始偏移 0 ： 窗口滑动过程： left=0, right=0 ，单词 "bar" 在 wordCount 中， windowCount={"bar":1} , count=1 。 right=3 ，单词 "foo" 在表中， windowCount={"bar":1,"foo":1} , count=2 ，找到匹配，记录 left=0 。 窗口右移， left=3, right=6 ，单词 "the" 不在表中，重置窗口， left=9 ，继续扫描... 最终在 left=9 找到第二个匹配。 起始偏移 1 和 2 也会扫描，但本例中没有额外匹配。 结果： [0,9] 关键点总结 因为单词长度相同，可以将问题转化为 固定长度片段的多模式匹配 。 滑动窗口时，以单词长度为单位移动，但需要从不同的字符偏移开始，确保不遗漏。 用两个哈希表分别记录目标词频和窗口词频，通过计数器判断窗口是否匹配。 时间复杂度：外层循环 wordLen 次，内层滑动窗口线性扫描，总体 O(wordLen * (n/wordLen)) = O(n) 。 空间复杂度： O(numWords * wordLen) 用于存储哈希表。 扩展思考 如果 words 中有很多重复单词，算法依然有效，因为哈希表记录的是次数。 如果 s 非常长， words 很多，但 wordLen 较小，算法仍然高效。 可以进一步优化：当遇到不在字典的单词时，可以直接跳过后，因为包含该单词的任何窗口都不可能匹配。