尧图网站建设 
1. 问题背景与核心挑战LeetCode第30题串联所有单词的子串是字符串处理类题目中的经典难题。给定一个字符串s和一个字符串数组words要求找出s中所有恰好由words中所有单词串联形成的子串的起始索引。words中的单词长度相同且可能重复。这个问题的难点在于需要同时满足所有单词的完整出现包括重复单词单词可以以任意顺序排列子串必须严格连续且不包含其他字符输入规模可能很大s长度可达10^4words长度可达50002. 解题思路分析2.1 暴力解法及其缺陷最直观的解法是生成words所有可能的排列组合在s中搜索每个组合的出现位置但这种方法时间复杂度为O(N!×M)其中N是words长度M是s长度。当N10时10! 3628800完全不可行。2.2 滑动窗口哈希计数的优势更优的解法结合了滑动窗口和哈希计数利用所有单词长度相同的特点设为word_len将问题转化为在s中寻找长度为word_len×words_num的子串使用哈希表记录words中每个单词的出现次数滑动窗口检查每个候选子串是否符合要求这种方法将时间复杂度降为O(N×M)空间复杂度O(N)。3. 详细实现步骤3.1 预处理阶段from collections import defaultdict def findSubstring(s, words): if not s or not words: return [] word_len len(words[0]) total_len word_len * len(words) word_count defaultdict(int) for word in words: word_count[word] 1关键点先处理边界情况空输入计算单个单词长度和总子串长度使用defaultdict统计每个单词出现次数3.2 滑动窗口实现result [] n len(s) for i in range(word_len): left i curr_count defaultdict(int) count 0 for j in range(i, n - word_len 1, word_len): word s[j:jword_len] if word in word_count: curr_count[word] 1 count 1 while curr_count[word] word_count[word]: left_word s[left:leftword_len] curr_count[left_word] - 1 left word_len count - 1 if count len(words): result.append(left) left_word s[left:leftword_len] curr_count[left_word] - 1 left word_len count - 1 else: curr_count.clear() count 0 left j word_len return result代码解析外层循环处理不同起始位置0到word_len-1维护窗口[left, j]和当前计数curr_count当发现不在words中的单词时重置窗口当某个单词超额时移动左边界直到合规当count等于words长度时记录有效索引4. 关键优化技巧4.1 窗口移动的步长优化由于所有单词长度相同窗口可以以word_len为步长移动而不是逐字符移动。这使得时间复杂度从O(M×N)降为O(M×word_len)。4.2 哈希表的快速比对使用两个哈希表word_count记录words的标准分布curr_count记录当前窗口的实际分布通过比较两个哈希表是否相同来判断窗口有效性比字符串拼接比较效率高得多。4.3 提前终止条件当剩余字符串长度不足total_len时可以提前终止搜索避免无意义的检查。5. 边界情况处理5.1 输入为空的情况if not s or not words: return []5.2 单词长度不一致题目已保证words中所有单词长度相同但实际工程中需要验证if any(len(w) ! word_len for w in words): return []5.3 超长输入处理对于特别长的s和words可以考虑先检查s长度是否足够使用更高效的数据结构如原生dict代替defaultdict6. 复杂度分析时间复杂度O(word_len × n)。外层循环word_len次内层最多处理n/word_len次。空间复杂度O(m)。需要存储words的哈希表m为words中不同单词的数量。7. 实际测试案例测试用例1s barfoothefoobarman words [foo,bar] # 输出[0,9]测试用例2s wordgoodgoodgoodbestword words [word,good,best,word] # 输出[]测试用例3s a * 10000 words [a] * 5000 # 需要高效处理大规模输入8. 常见错误与调试技巧8.1 窗口边界错误典型错误没有正确处理窗口左边界移动导致遗漏或重复计数。调试方法打印窗口变化时的left, j和curr_count使用小测试用例逐步跟踪8.2 哈希表比对错误常见问题直接比较两个defaultdict对象可能不如预期。解决方案转换为普通dict再比较或者逐个键值比较8.3 性能优化技巧当words有很多重复单词时可以先统计unique单词对s预处理建立单词位置索引使用位图等压缩存储方式9. 算法扩展思考9.1 变体问题单词长度不同如果words中单词长度不同问题会更复杂。可能的解法使用回溯法尝试所有组合结合Trie树进行模式匹配9.2 实际应用场景这种算法可用于DNA序列模式查找文档内容指纹识别网络流量特征检测10. 个人实现心得在实际编码中发现几个关键点窗口移动时要同时更新计数和窗口大小Python的defaultdict在清空时最好重新初始化避免残留数据对于超长重复字符串可以先检查首字符是否匹配再进行完整比较在竞赛中可以预先计算所有可能的单词哈希值加速比较一个容易忽略的优化当words中存在重复单词时可以先对words排序然后在滑动窗口中对截取的单词也排序后比较虽然增加了排序开销但减少了哈希表操作。 LeetCode 30题解析：滑动窗口与哈希计数优化
1. 问题背景与核心挑战LeetCode第30题串联所有单词的子串是字符串处理类题目中的经典难题。给定一个字符串s和一个字符串数组words要求找出s中所有恰好由words中所有单词串联形成的子串的起始索引。words中的单词长度相同且可能重复。这个问题的难点在于需要同时满足所有单词的完整出现包括重复单词单词可以以任意顺序排列子串必须严格连续且不包含其他字符输入规模可能很大s长度可达10^4words长度可达50002. 解题思路分析2.1 暴力解法及其缺陷最直观的解法是生成words所有可能的排列组合在s中搜索每个组合的出现位置但这种方法时间复杂度为O(N!×M)其中N是words长度M是s长度。当N10时10! 3628800完全不可行。2.2 滑动窗口哈希计数的优势更优的解法结合了滑动窗口和哈希计数利用所有单词长度相同的特点设为word_len将问题转化为在s中寻找长度为word_len×words_num的子串使用哈希表记录words中每个单词的出现次数滑动窗口检查每个候选子串是否符合要求这种方法将时间复杂度降为O(N×M)空间复杂度O(N)。3. 详细实现步骤3.1 预处理阶段from collections import defaultdict def findSubstring(s, words): if not s or not words: return [] word_len len(words[0]) total_len word_len * len(words) word_count defaultdict(int) for word in words: word_count[word] 1关键点先处理边界情况空输入计算单个单词长度和总子串长度使用defaultdict统计每个单词出现次数3.2 滑动窗口实现result [] n len(s) for i in range(word_len): left i curr_count defaultdict(int) count 0 for j in range(i, n - word_len 1, word_len): word s[j:jword_len] if word in word_count: curr_count[word] 1 count 1 while curr_count[word] word_count[word]: left_word s[left:leftword_len] curr_count[left_word] - 1 left word_len count - 1 if count len(words): result.append(left) left_word s[left:leftword_len] curr_count[left_word] - 1 left word_len count - 1 else: curr_count.clear() count 0 left j word_len return result代码解析外层循环处理不同起始位置0到word_len-1维护窗口[left, j]和当前计数curr_count当发现不在words中的单词时重置窗口当某个单词超额时移动左边界直到合规当count等于words长度时记录有效索引4. 关键优化技巧4.1 窗口移动的步长优化由于所有单词长度相同窗口可以以word_len为步长移动而不是逐字符移动。这使得时间复杂度从O(M×N)降为O(M×word_len)。4.2 哈希表的快速比对使用两个哈希表word_count记录words的标准分布curr_count记录当前窗口的实际分布通过比较两个哈希表是否相同来判断窗口有效性比字符串拼接比较效率高得多。4.3 提前终止条件当剩余字符串长度不足total_len时可以提前终止搜索避免无意义的检查。5. 边界情况处理5.1 输入为空的情况if not s or not words: return []5.2 单词长度不一致题目已保证words中所有单词长度相同但实际工程中需要验证if any(len(w) ! word_len for w in words): return []5.3 超长输入处理对于特别长的s和words可以考虑先检查s长度是否足够使用更高效的数据结构如原生dict代替defaultdict6. 复杂度分析时间复杂度O(word_len × n)。外层循环word_len次内层最多处理n/word_len次。空间复杂度O(m)。需要存储words的哈希表m为words中不同单词的数量。7. 实际测试案例测试用例1s barfoothefoobarman words [foo,bar] # 输出[0,9]测试用例2s wordgoodgoodgoodbestword words [word,good,best,word] # 输出[]测试用例3s a * 10000 words [a] * 5000 # 需要高效处理大规模输入8. 常见错误与调试技巧8.1 窗口边界错误典型错误没有正确处理窗口左边界移动导致遗漏或重复计数。调试方法打印窗口变化时的left, j和curr_count使用小测试用例逐步跟踪8.2 哈希表比对错误常见问题直接比较两个defaultdict对象可能不如预期。解决方案转换为普通dict再比较或者逐个键值比较8.3 性能优化技巧当words有很多重复单词时可以先统计unique单词对s预处理建立单词位置索引使用位图等压缩存储方式9. 算法扩展思考9.1 变体问题单词长度不同如果words中单词长度不同问题会更复杂。可能的解法使用回溯法尝试所有组合结合Trie树进行模式匹配9.2 实际应用场景这种算法可用于DNA序列模式查找文档内容指纹识别网络流量特征检测10. 个人实现心得在实际编码中发现几个关键点窗口移动时要同时更新计数和窗口大小Python的defaultdict在清空时最好重新初始化避免残留数据对于超长重复字符串可以先检查首字符是否匹配再进行完整比较在竞赛中可以预先计算所有可能的单词哈希值加速比较一个容易忽略的优化当words中存在重复单词时可以先对words排序然后在滑动窗口中对截取的单词也排序后比较虽然增加了排序开销但减少了哈希表操作。