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排序然后在滑动窗口中对截取的单词也排序后比较虽然增加了排序开销但减少了哈希表操作。
企业数字化 ERP 产品动态
相关推荐
定向耦合器速查手册：3步搞定微波仿真配置痛点 定向耦合器速查手册：3步搞定微波仿真配置痛点 配置微波仿真环境时，是不是经常卡在参数设置上半天？S参数提取不对、隔离度计算报错、端口阻抗匹配失败，这些坑我全踩过。这份 定向耦合器… · 2026/9/23 2:50:24
Android Loader异步加载器解析：TaoToken统一Key接入与配置验证 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/23 2:50:24
Calypso Dashboard 组件测试实战指南：以用户可见行为为中心的 Testing Library 规范 前端CMS 【免费下载链接】wp-calypso The JavaScript and API powered WordPress.com 项目地址： https://gitcode.com/gh_mirrors/wp/wp-calypso 点击查看 免费下载 Calypso（wp-calypso）是 WordPress.com 的 JavaScript 前端，其新… · 2026/9/23 2:50:24
AI痕迹太重？四层去痕法让文章自然如真人写作 写作者最头疼的一个场景，大概就是你辛辛苦苦用AI写了篇文章，回头自己读一遍，越读越别扭——句子全对，逻辑没毛病，但就是一股“机器味”，一眼假。这种情况我太熟了。这两年我不管写公众号、改工作报告&#… · 2026/9/23 3:34:50
语言代理如何学会“攒经验”？ELAE早期经验机制详解与落地实践 不用急着去调参，也别急着上复杂业务，最近Meta放出的Agent Learning via Early Experience（ELAE）研究思路，值得每一个做语言代理应用的人停下来想一想：我们是不是一直没教会智能体“学习”，只是让… · 2026/9/23 3:34:50
脸上雀斑怎么去除速查手册：3个致命坑让你代码跑不通 脸上雀斑怎么去除速查手册：3个致命坑让你代码跑不通 刚把网上那段“脸上雀斑怎么去除”的Python脚本复制下来，双击运行，终端直接报 ModuleNotFoundError… · 2026/9/23 3:34:50
MATLAB纯CNN水域分割实战：从零手搭6层网络与像素级评估 简介：本资源是一套面向本硕博及教研人员的MATLAB实践型学习材料，聚焦卷积神经网络（CNN）在遥感或水体监测图像分割任务中的落地实现，解决水域区域精准识别与算法可视化验证问题。压缩包共64个文件，含39个核心… · 2026/9/23 3:34:50
3分钟看懂譬如的意思源码解析与避坑 3分钟看懂譬如的意思源码解析与避坑 版本升级后 API 全变了，这种崩溃感谁懂？很多应届生在重构旧项目时，发现原本熟悉的函数签名彻底消失，文档也没更新。这时候，光看表面报错没用，得直接钻进去看 源码解析… · 2026/9/23 3:34:43
3招搞定手机怎么下载微信面试难题实战项目解析 3招搞定手机怎么下载微信面试难题实战项目解析 面试被问“手机怎么下载微信”背后的原理，90%的人答不上来。别笑，这看似弱智的问题，实则是考察你对移动应用分发机制、安全校验及网络协议理解的试金石。我带过不少校招新人，他们背了八股文，却连一个A… · 2026/9/23 0:00:03
你有新短消息请注意查收：3个新手避坑指南搞定消息系统选型 你有新短消息请注意查收：3个新手避坑指南搞定消息系统选型 面试被问“高并发下如何保证消息不丢失”，你张口就是“用Redis”，结果面试官追问“如果Redis宕机了怎么办”，你瞬间卡壳。这种场景太常见了，很多新手在背八股文时，只记住了技术名词… · 2026/9/23 0:00:29
