1. 问题背景与核心挑战这道LeetCode Hard题目要求我们找到一个字符串中所有满足特定条件的子串起始位置。具体来说给定一个字符串s和一个单词列表words其中所有单词长度相同。我们需要找出s中所有可以由words中所有单词按任意顺序串联形成的子串的起始索引。举个例子假设s barfoothefoobarmanwords [foo, bar]。我们需要找到的子串是barfoo起始索引0和foobar起始索引9因为它们都是由words中所有单词串联而成顺序可以不同。这个问题的难点在于需要处理单词的任意排列组合所有单词必须完整出现且不重叠需要考虑滑动窗口的多种可能情况时间复杂度优化是关键暴力解法很容易超时2. 解题思路分析与算法选择2.1 暴力解法及其缺陷最直观的解法是生成words所有可能的排列组合在s中搜索每个组合的起始位置但这种方法的复杂度是O(N! * M)其中N是words长度M是s长度。当N10时10! 3,628,800显然不可行。2.2 滑动窗口与哈希表的结合更聪明的做法是采用滑动窗口配合哈希表统计计算单个单词长度word_len和总串联长度total_len创建words的频次哈希表word_count遍历s中所有可能的起始位置0到s.length()-total_len对每个起始位置检查接下来的total_len长度是否能被拆分为words的某种排列这种方法将复杂度降到了O(M * N)其中M是s长度N是words长度。2.3 进一步的优化思路我们可以通过以下优化进一步提升效率预处理words的哈希表避免重复计算利用单词长度固定的特性可以跳跃式检查当发现不匹配时立即终止当前窗口的检查3. 详细实现步骤与代码解析3.1 初始化与预处理def findSubstring(s, words): if not s or not words: return [] word_len len(words[0]) total_len word_len * len(words) word_count {} for word in words: word_count[word] word_count.get(word, 0) 1首先检查输入是否有效然后计算单个单词长度和总串联长度。创建word_count字典统计每个单词的出现次数。3.2 主循环与滑动窗口实现result [] for i in range(len(s) - total_len 1): seen {} j 0 while j len(words): word s[i j * word_len : i (j 1) * word_len] if word in word_count: seen[word] seen.get(word, 0) 1 if seen[word] word_count[word]: break else: break j 1 if j len(words): result.append(i) return result主循环遍历所有可能的起始位置。对每个位置检查接下来的total_len长度是否能拆分为words的某种排列使用seen字典记录当前窗口内单词出现次数如果某个单词出现次数超过word_count中的值立即终止如果成功检查完所有单词记录当前起始位置3.3 复杂度分析时间复杂度O(M * N)其中M是s长度N是words长度空间复杂度O(N)用于存储word_count和seen字典4. 优化方案与性能提升4.1 多起点滑动窗口优化原始解法对每个起始位置都重新检查存在重复计算。我们可以改进为def findSubstring(s, words): if not s or not words: return [] word_len len(words[0]) total_len word_len * len(words) word_count {} for word in words: word_count[word] word_count.get(word, 0) 1 result [] for k in range(word_len): left k curr_count {} count 0 for j in range(k, len(s) - word_len 1, word_len): word s[j:j word_len] if word in word_count: curr_count[word] curr_count.get(word, 0) 1 count 1 while curr_count[word] word_count[word]: left_word s[left:left word_len] curr_count[left_word] - 1 left word_len count - 1 if count len(words): result.append(left) else: curr_count.clear() count 0 left j word_len return result这种优化从不同偏移量0到word_len-1开始滑动窗口维护一个动态的窗口只在必要时移动左边界减少了重复检查平均复杂度接近O(M)4.2 边界条件处理在实际编码中需要特别注意以下边界条件输入字符串为空单词列表为空所有单词长度不一致题目已保证字符串长度小于总串联长度单词包含重复项5. 测试用例设计与验证5.1 基础测试用例# 示例1 s barfoothefoobarman words [foo,bar] # 预期输出 [0,9] # 示例2 s wordgoodgoodgoodbestword words [word,good,best,word] # 预期输出 [] # 示例3 s a words [a] # 预期输出 [0]5.2 边缘测试用例# 空输入 s words [test] # 预期输出 [] # 字符串长度不足 s short words [longword] # 预期输出 [] # 重复单词 s wordwordwordword words [word,word] # 预期输出 [0,4,8]5.3 性能测试用例# 长字符串重复模式 s a * 10000 b * 10000 words [a * 100, b * 100] # 需要验证算法效率6. 常见错误与调试技巧6.1 典型错误模式索引越界忘记检查字符串长度是否足够# 错误示例 for i in range(len(s)): # 应该减去total_len ...单词计数错误没有正确处理重复单词# 错误示例 if word in seen: # 应该比较出现次数 break窗口滑动错误移动步长不正确# 错误示例 i 1 # 应该按word_len移动6.2 调试建议打印中间变量print(fi{i}, word{word}, seen{seen})使用小测试用例逐步验证先测试单个单词的情况再测试无重复单词的情况最后测试有重复单词的复杂情况可视化滑动窗口 在纸上画出字符串和窗口移动过程有助于理解算法逻辑7. 实际应用场景与变种问题7.1 实际应用场景这种算法可以应用于基因序列中的模式查找文档中的短语搜索网络流量中的特征匹配大规模文本中的关键词检测7.2 相关变种问题允许部分匹配不要求匹配所有单词而是匹配其中若干个变长单词单词长度可以不同难度大幅增加模糊匹配允许少量字符不匹配多字符串搜索同时搜索多个不同的单词组合8. 个人解题心得与建议在解决这个问题时我总结了以下几点经验先理解再编码一定要完全理解题目要求特别是任意顺序串联的含义从暴力解法开始即使知道暴力解法不好先实现它可以帮助理解问题本质画图辅助滑动窗口问题用图示法特别有效优化要循序渐进先保证正确性再考虑优化边界测试很重要特别是空输入、极短字符串等情况容易忽略对于LeetCode练习我建议先独立思考至少30分钟写出伪代码或解题思路实现基础解法后再看讨论区的优化方案记录每道题的解题时间和遇到的问题
