作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读 公众号 数据分析螺丝钉 一起打怪升级
问题描述
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要包含所有的单词，且不能有重复和遗漏。
示例 1：
输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar"。 输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[]
1.滑动窗口+哈希表
这是一个查找子串的问题，可以通过滑动窗口配合哈希表来解决。主要思路是：
- 建立词频表：首先统计
words数组中各单词的频率。 - 滑动窗口搜索：由于单词长度固定，我们可以每次移动一个单词的长度，而不是逐个字符移动。对于每个可能的单词起始位置（0 到单词长度），使用滑动窗口检查是否可以匹配
words中的所有单词。 - 匹配验证：使用另一个哈希表记录窗口中单词的出现次数，如果与
words的词频表相匹配，则记录当前开始位置。
代码示例
def findSubstring(s: str, words: list) -> list: from collections import Counter if not s or not words: return [] word_len = len(words[0]) word_count = len(words) total_len = word_len * word_count words_count = Counter(words) def check(start): seen = Counter() # 检查每个窗口内的单词频率 for i in range(start, start + total_len, word_len): word = s[i:i + word_len] if word in words_count: seen[word] += 1 if seen[word] > words_count[word]: return False else: return False return True results = [] # 只需要检查 word_len 种情况 for i in range(word_len): for j in range(i, len(s) - total_len + 1, word_len): if check(j): results.append(j) return results # 测试代码 s1 = "barfoothefoobarman" words1 = ["foo","bar"] print(findSubstring(s1, words1)) # Output: [0, 9] s2 = "wordgoodgoodgoodbestword" words2 = ["word","good","best","word"] print(findSubstring(s2, words2)) # Output: []
算法分析
- 时间复杂度：O(N * M * L)，其中 N 是字符串
s的长度，M 是words数组的长度，L 是每个单词的长度。 - 空间复杂度：O(M)，主要是词频表的空间消耗。
算法图解
考虑滑动窗口的初步设置，如下图所示：
Initial string: barfoothefoobarman |______| barfoo
步骤 1: 检查从索引 0 开始的子串
- 滑动窗口覆盖
"barfoo"(从索引 0 到 5) - 分解为
["bar", "foo"]，与words_count对比，发现匹配，因此索引 0 是有效的。
图示：
barfoothefoobarman |______| barfoo
步骤 2: 滑动到下一个可能的起始点
- 从索引 3 开始，但
"footh"不符合任何有效组合，跳过。
图示：
barfoothefoobarman |______| footh
步骤 3: 继续滑动到索引 6
- 从索引 6 开始的
"thefo"同样不符合，继续。
图示：
barfoothefoobarman |______| thefo
步骤 4: 检查从索引 9 开始的子串
- 滑动窗口覆盖
"foobar"(从索引 9 到 14) - 分解为
["foo", "bar"]，与words_count对比，发现匹配，因此索引 9 是有效的。
图示：
barfoothefoobarman |______| foobar
结果
- 正确的起始索引为
[0, 9]。
2.双指针 + 哈希表
双指针技术可以与哈希表结合使用来优化搜索过程。这种方法主要是通过一个左右指针（或称为滑动窗口）来维护当前考察的子串，通过动态调整左右指针来尝试包含所有单词的连续段。
实现思路：
- 使用两个指针
start和end初始化在字符串的开始位置。 - 使用一个哈希表来记录窗口内单词的出现频率和另一个哈希表来记录
words数组的单词频率。 - 移动
end指针来扩展窗口直到窗口内包含了words的所有单词。 - 一旦窗口有效，尝试通过移动
start指针来缩小窗口大小，同时保持窗口的有效性。 - 记录所有有效窗口的起始位置。
代码示例
from collections import Counter, defaultdict def findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) word_count = len(words) total_len = word_len * word_count words_count = Counter(words) def is_valid(start): seen = defaultdict(int) for i in range(word_count): word = s[start + i*word_len:start + (i+1)*word_len] if word in words_count: seen[word] += 1 if seen[word] > words_count[word]: return False else: return False return True results = [] # 只需要检查 word_len 种情况 for i in range(word_len): left = i while left <= len(s) - total_len: if is_valid(left): results.append(left) left += word_len # 移动一个单词的长度 return results # 测试代码 s1 = "barfoothefoobarman" words1 = ["foo", "bar"] print(findSubstring(s1, words1)) # Output: [0, 9] s2 = "wordgoodgoodgoodbestword" words2 = ["word","good","best","word"] print(findSubstring(s2, words2)) # Output: []
算法分析
时间复杂度：最坏情况 O((N - M * L) * M * L)，其中 N 是字符串 s 的长度，M 是 words 中的单词数量，L 是每个单词的长度。这是因为每个起始位置需要 O(M\*L) 的时间来验证窗口内的字符串，并且有 N−M\*L 个这样的起始位置。
空间复杂度：O(M) 主要空间消耗来源于两个哈希表，一个是 words_count 用于存储单词的目标频率，另一个是 seen 用于实时统计当前窗口内单词的出现频率。
3. 索引哈希映射
这种方法侧重于通过索引哈希映射优化单词的查找过程，这可以减少重复的字符串比较。
实现思路：
- 首先对
words中的每个单词建立其索引的映射。 - 对输入字符串
s使用相同的单词长度进行分割，将每个可能的单词与words哈希映射进行对比。 - 使用一个滑动窗口，窗口大小为所有
words单词长度的总和，通过窗口内的单词索引快速检查是否满足条件。
代码示例
from collections import Counter, defaultdict def findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) word_count = len(words) total_len = word_len * word_count words_count = Counter(words) # 生成单词到可能起始索引的映射 word_to_index = defaultdict(list) for i in range(len(s) - word_len + 1): word = s[i:i + word_len] if word in words_count: word_to_index[word].append(i) results = [] # 遍历每个单词长度的偏移 for offset in range(word_len): for start in range(offset, len(s) - total_len + 1, word_len): valid = True seen = Counter() # 遍历每个单词位置，检查是否满足条件 for i in range(word_count): word_index = start + i * word_len word = s[word_index:word_index + word_len] if word in words_count: seen[word] += 1 if seen[word] > words_count[word]: valid = False break else: valid = False break if valid: results.append(start) return results # 测试代码 s1 = "barfoothefoobarman" words1 = ["foo", "bar"] print(findSubstring(s1, words1)) # Output: [0, 9] s2 = "wordgoodgoodgoodbestword" words2 = ["word","good","best","word"] print(findSubstring(s2, words2)) # Output: []
算法分析
时间复杂度 O((N - L * M) * L * M): 其中 N 是字符串 s 的长度，M 是 words 的长度（单词数量），L 是每个单词的长度。时间复杂度主要由两部分组成：
- 建立哈希映射：需要遍历字符串
s一次，时间复杂度为 O(N)。 - 检查每个可能的起始位置：对于每个可能的起始位置，需要 O(M\*L) 的时间来验证是否所有单词都符合要求。
空间复杂度 O(N): 主要空间消耗来源于 word_to_index 哈希映射，它在最坏情况下可能包含接近 s 的长度的索引，尤其是当 s 包含大量属于 words 的单词时。
4. Rabin-Karp 字符串哈希
利用 Rabin-Karp 算法的字符串哈希技术可以快速在主串中找到匹配的子串，这对于连续匹配检查尤其有效。
实现思路：
- 计算
words中所有单词组合的哈希值。 - 使用滑动哈希技术在
s中滑动，计算每个长度为total_len的子串的哈希值。 - 对于每个哈希值匹配的位置，验证其是否真正由
words中的单词组成。
代码示例
from collections import Counter def findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) word_count = len(words) total_len = word_len * word_count results = [] # 计算words中所有单词的哈希值总和 words_hash = sum([hash(word) for word in words]) current_hash = 0 # 预处理第一个窗口的哈希值 for i in range(total_len): current_hash += hash(s[i:i+word_len]) # 滑动窗口 for start in range(len(s) - total_len + 1): if current_hash == words_hash: # 如果哈希值匹配，验证实际字符串 if Counter([s[start+i*word_len:start+(i+1)*word_len] for i in range(word_count)]) == Counter(words): results.append(start) if start < len(s) - total_len: # 更新哈希值：移除旧的，添加新的 current_hash -= hash(s[start:start+word_len]) current_hash += hash(s[start+total_len:start+total_len+word_len]) return results # 测试代码 s = "barfoothefoobarman" words = ["foo", "bar"] print(findSubstring(s, words)) # Output: [0, 9]
算法分析
时间复杂度 O((N - M * L) * M * L): 其中 N 是字符串 s 的长度，M 是 words 的长度（单词数量），L 是每个单词的长度。主要开销来源于：
- 初始窗口的哈希计算：O(M\*L)。
- 每次窗口滑动的更新和验证：O(M\*L)。
空间复杂度 O(M * L): 主要空间消耗来源于存储 words 的哈希值和滑动窗口中单词的哈希值。
结论
滑动窗口 + 哈希表：使用滑动窗口检查每个可能的子串，通过哈希表快速统计和比较单词频率。适合于快速检索，但可能在某些情况下效率不高。
双指针 + 哈希表：结合双指针技术和哈希表进行精确的窗口控制和单词计数，优化窗口调整过程，提高检索效率。
索引哈希映射：预先建立单词与其在字符串中索引的映射，降低运算量，减少重复的字符串比较，虽增加空间复杂度但提升查询速度。
Rabin-Karp 算法：是一个通过哈希技术高效处理字符串搜索问题的方法。它特别适合于在一个较大的文本中搜索一个或多个固定大小的模式串
在实际的面试和算法设计中，类似的技巧可以广泛应用于其他字符串匹配和分析问题。
欢迎关注微信公众号 数据分析螺丝钉
