【LeetCode 30.串联所有单词的子串】滑动窗口哈希表 最优解超详细题解专栏LeetCode算法题解滑动窗口哈希表专项难度困难标签#滑动窗口 #哈希表 #字符串 #LeetCode30 #双指针一、问题描述给定一个字符串s和一个字符串数组wordswords 中所有字符串长度完全相同。串联子串定义字符串s中包含words所有字符串且以任意顺序排列连接形成的子串子串中不能包含多余字符每个单词只能出现一次且次数与原数组一致。要求返回所有串联子串在s中的起始索引答案顺序可任意若无符合条件的子串返回空数组。示例演示示例 1输入输出示例输入s barfoothefoobarman, words [foo,bar] 输出[0,9]解释words数组长度为2每个单词长度为3因此串联子串总长度固定为6。起始位置0的子串barfoo、起始位置9的子串foobar均为words的有效排列组合符合要求。示例 2输入输出示例输入s wordgoodgoodgoodbestword, words [word,good,best,word] 输出[]解释串联子串需包含2个word、1个good、1个best原字符串中无匹配子串返回空数组。示例 3输入输出示例输入s barfoofoobarthefoobarman, words [bar,foo,the] 输出[6,9,12]题目提示与数据范围1 s.length 10^4字符串长度适中需控制时间复杂度避免超时1 words.length 5000单词数组规模较大暴力法易超时1 lt; words[i].length lt; 30所有单词长度一致核心优化点s和words[i]仅由小写英文字母组成无需处理大小写问题二、解题思路深度分析2.1 暴力解法弊端为何不选暴力思路枚举s中所有长度为总长度单词数×单词长度的子串拆分后判断是否与words完全匹配。但这种方法需要频繁拆分字符串、重复统计词频时间复杂度高达O(N×M×K)N为s长度M为单词数K为单词长度面对大数据量会直接超时无法通过所有测试用例。2.2 核心优化思路滑动窗口哈希表本题核心突破口words中所有单词长度相同设单个单词长度为word_len单词总数为word_cnt串联子串总长度为total_len word_len × word_cnt。我们无需逐个字符遍历而是按单词长度分组滑动将字符串拆分为word_len组每组内以word_len为步长滑动窗口用哈希表统计窗口内单词频次与words的词频哈希表对比快速判断是否匹配大幅降低重复计算。核心原理词频统计先用哈希表统计words中每个单词的出现次数作为基准词频分组滑动按单词长度分组每组起始位置为0、1、…、word_len-1避免重复拆分窗口匹配维护固定长度的滑动窗口窗口内单词数等于word_cnt实时统计词频与基准词频一致则记录起始索引动态调整窗口内单词频次超标时移动左指针缩小窗口保证窗口内单词有效2.3 算法复杂度分析时间复杂度O(N)N为字符串s长度每组仅遍历一次总操作数与字符串长度线性相关空间复杂度O(M×K)M为单词数K为单词长度用于存储哈希表属于合理空间开销关键优化点按单词长度分组滑动而非逐个字符滑动彻底避免重复拆分和词频统计解决大数据量超时问题这是本题从暴力到最优的核心转变。三、完整代码实现标准格式LeetCode 30 滑动窗口哈希表最优解from typing import List from collections import defaultdict class Solution: def findSubstring(self, s: str, words: List[str]) - List[int]: # 处理特殊边界空字符串或空单词数组 if not s or not words: return [] # 定义核心参数 s_len len(s) # 字符串总长度 word_len len(words[0]) # 单个单词长度题目保证所有单词等长 word_cnt len(words) # 单词总数 total_len word_len * word_cnt # 串联子串总长度 res [] # 存储结果索引 # 统计基准词频words中每个单词的出现次数 word_count defaultdict(int) for word in words: word_count[word] 1 # 按单词长度分组每组起始位置为0到word_len-1避免重复遍历 for i in range(word_len): left i # 窗口左指针 cur_count defaultdict(int) # 统计当前窗口内单词频次 match_cnt 0 # 记录窗口内匹配基准词频的单词数 # 右指针以单词长度为步长滑动 for right in range(i, s_len - word_len 1, word_len): # 截取当前单词 cur_word s[right:rightword_len] # 如果当前单词不在基准词频中直接重置窗口 if cur_word not in word_count: cur_count.clear() match_cnt 0 left right word_len continue # 将当前单词加入窗口 cur_count[cur_word] 1 # 如果当前单词频次不超过基准匹配数1 if cur_count[cur_word] word_count[cur_word]: match_cnt 1 # 当窗口内单词数量超过总单词数收缩左指针 while right - left word_len total_len: left_word s[left:leftword_len] # 如果移出的单词刚好是匹配的匹配数-1 if cur_count[left_word] word_count[left_word]: match_cnt - 1 cur_count[left_word] - 1 left word_len # 匹配数等于单词种类数说明找到有效子串 if match_cnt len(word_count): res.append(left) return res四、代码逐行详解4.1 边界预处理先判断字符串s或words数组为空的情况直接返回空数组避免后续索引越界和无效计算。4.2 核心参数定义s_len字符串s总长度用于控制遍历范围word_len单个单词长度题目保证所有单词等长直接取第一个单词长度即可word_cntwords数组中单词总数确定窗口内需要的单词数量total_len串联子串固定总长度窗口长度必须等于该值4.3 基准词频统计用defaultdict统计words中每个单词的出现次数作为后续窗口匹配的基准解决单词重复出现的问题。4.4 分组滑动窗口核心逻辑外层循环按单词长度分组每组起始索引为0到word_len-1覆盖所有可能的拆分方式左指针固定每组起始位置右指针以word_len为步长滑动截取窗口内单词若当前单词不在基准词频中直接清空当前窗口重置左指针跳过无效区间实时更新窗口内词频统计匹配成功的单词数量窗口超出总长度时收缩左指针移除左侧单词保证窗口长度固定匹配数等于基准词频的种类数时记录左指针为有效起始索引4.5 结果返回遍历结束后返回存储所有有效起始索引的结果数组。五、测试用例逐行推演示例1推演s “barfoothefoobarman”, words [“foo”,“bar”]核心参数word_len3word_cnt2total_len6基准词频{“foo”:1, “bar”:1}分组遍历i0、1、2i0组右指针滑动截取bar、“foo”窗口匹配记录索引0后续滑动截取the、“foo”、“bar”窗口再次匹配记录索引9最终结果[0,9]示例2推演s “wordgoodgoodgoodbestword”, words [“word”,“good”,“best”,“word”]基准词频{“word”:2, “good”:1, “best”:1}字符串中仅含1个word无窗口能匹配词频结果为空数组六、边界情况全覆盖处理6.1 极端边界场景s长度等于串联子串长度直接判断整体是否匹配words仅含一个单词查找s中所有该单词的起始索引words含重复单词哈希表正常统计频次窗口严格匹配次数s中无有效子串返回空数组6.2 边界测试用例# 用例1单个单词 s aaa, words [a] → 输出[0,1,2] # 用例2s长度等于总长度 s abcdef, words [abc,def] → 输出[0] # 用例3无匹配子串 s abcd, words [ef] → 输出[]七、核心总结与拓展7.1 解题核心要点抓住固定单词长度利用题目“所有单词等长”的条件分组滑动窗口避免暴力枚举哈希表词频对比快速判断窗口内单词是否匹配解决重复单词和乱序匹配问题滑动窗口动态调整保证窗口长度固定实时维护词频时间复杂度最优7.2 同类题型拓展本题是滑动窗口哈希表的经典困难题适配场景字符串子串匹配问题词频统计与排列组合匹配固定长度/可变长度滑动窗口问题易错点提醒1. 忘记按单词长度分组导致超时2. 未处理words中重复单词词频统计错误3. 窗口收缩时匹配数更新错误导致结果漏判或多判。原创不易觉得有用的话欢迎点赞、收藏、关注后续持续更新LeetCode高频题解、滑动窗口/哈希表技巧和面试真题解析
【LeetCode 30.串联所有单词的子串】滑动窗口+哈希表 最优解｜超详细题解
【LeetCode 30.串联所有单词的子串】滑动窗口哈希表 最优解超详细题解专栏LeetCode算法题解滑动窗口哈希表专项难度困难标签#滑动窗口 #哈希表 #字符串 #LeetCode30 #双指针一、问题描述给定一个字符串s和一个字符串数组wordswords 中所有字符串长度完全相同。串联子串定义字符串s中包含words所有字符串且以任意顺序排列连接形成的子串子串中不能包含多余字符每个单词只能出现一次且次数与原数组一致。要求返回所有串联子串在s中的起始索引答案顺序可任意若无符合条件的子串返回空数组。示例演示示例 1输入输出示例输入s barfoothefoobarman, words [foo,bar] 输出[0,9]解释words数组长度为2每个单词长度为3因此串联子串总长度固定为6。起始位置0的子串barfoo、起始位置9的子串foobar均为words的有效排列组合符合要求。示例 2输入输出示例输入s wordgoodgoodgoodbestword, words [word,good,best,word] 输出[]解释串联子串需包含2个word、1个good、1个best原字符串中无匹配子串返回空数组。示例 3输入输出示例输入s barfoofoobarthefoobarman, words [bar,foo,the] 输出[6,9,12]题目提示与数据范围1 s.length 10^4字符串长度适中需控制时间复杂度避免超时1 words.length 5000单词数组规模较大暴力法易超时1 lt; words[i].length lt; 30所有单词长度一致核心优化点s和words[i]仅由小写英文字母组成无需处理大小写问题二、解题思路深度分析2.1 暴力解法弊端为何不选暴力思路枚举s中所有长度为总长度单词数×单词长度的子串拆分后判断是否与words完全匹配。但这种方法需要频繁拆分字符串、重复统计词频时间复杂度高达O(N×M×K)N为s长度M为单词数K为单词长度面对大数据量会直接超时无法通过所有测试用例。2.2 核心优化思路滑动窗口哈希表本题核心突破口words中所有单词长度相同设单个单词长度为word_len单词总数为word_cnt串联子串总长度为total_len word_len × word_cnt。我们无需逐个字符遍历而是按单词长度分组滑动将字符串拆分为word_len组每组内以word_len为步长滑动窗口用哈希表统计窗口内单词频次与words的词频哈希表对比快速判断是否匹配大幅降低重复计算。核心原理词频统计先用哈希表统计words中每个单词的出现次数作为基准词频分组滑动按单词长度分组每组起始位置为0、1、…、word_len-1避免重复拆分窗口匹配维护固定长度的滑动窗口窗口内单词数等于word_cnt实时统计词频与基准词频一致则记录起始索引动态调整窗口内单词频次超标时移动左指针缩小窗口保证窗口内单词有效2.3 算法复杂度分析时间复杂度O(N)N为字符串s长度每组仅遍历一次总操作数与字符串长度线性相关空间复杂度O(M×K)M为单词数K为单词长度用于存储哈希表属于合理空间开销关键优化点按单词长度分组滑动而非逐个字符滑动彻底避免重复拆分和词频统计解决大数据量超时问题这是本题从暴力到最优的核心转变。三、完整代码实现标准格式LeetCode 30 滑动窗口哈希表最优解from typing import List from collections import defaultdict class Solution: def findSubstring(self, s: str, words: List[str]) - List[int]: # 处理特殊边界空字符串或空单词数组 if not s or not words: return [] # 定义核心参数 s_len len(s) # 字符串总长度 word_len len(words[0]) # 单个单词长度题目保证所有单词等长 word_cnt len(words) # 单词总数 total_len word_len * word_cnt # 串联子串总长度 res [] # 存储结果索引 # 统计基准词频words中每个单词的出现次数 word_count defaultdict(int) for word in words: word_count[word] 1 # 按单词长度分组每组起始位置为0到word_len-1避免重复遍历 for i in range(word_len): left i # 窗口左指针 cur_count defaultdict(int) # 统计当前窗口内单词频次 match_cnt 0 # 记录窗口内匹配基准词频的单词数 # 右指针以单词长度为步长滑动 for right in range(i, s_len - word_len 1, word_len): # 截取当前单词 cur_word s[right:rightword_len] # 如果当前单词不在基准词频中直接重置窗口 if cur_word not in word_count: cur_count.clear() match_cnt 0 left right word_len continue # 将当前单词加入窗口 cur_count[cur_word] 1 # 如果当前单词频次不超过基准匹配数1 if cur_count[cur_word] word_count[cur_word]: match_cnt 1 # 当窗口内单词数量超过总单词数收缩左指针 while right - left word_len total_len: left_word s[left:leftword_len] # 如果移出的单词刚好是匹配的匹配数-1 if cur_count[left_word] word_count[left_word]: match_cnt - 1 cur_count[left_word] - 1 left word_len # 匹配数等于单词种类数说明找到有效子串 if match_cnt len(word_count): res.append(left) return res四、代码逐行详解4.1 边界预处理先判断字符串s或words数组为空的情况直接返回空数组避免后续索引越界和无效计算。4.2 核心参数定义s_len字符串s总长度用于控制遍历范围word_len单个单词长度题目保证所有单词等长直接取第一个单词长度即可word_cntwords数组中单词总数确定窗口内需要的单词数量total_len串联子串固定总长度窗口长度必须等于该值4.3 基准词频统计用defaultdict统计words中每个单词的出现次数作为后续窗口匹配的基准解决单词重复出现的问题。4.4 分组滑动窗口核心逻辑外层循环按单词长度分组每组起始索引为0到word_len-1覆盖所有可能的拆分方式左指针固定每组起始位置右指针以word_len为步长滑动截取窗口内单词若当前单词不在基准词频中直接清空当前窗口重置左指针跳过无效区间实时更新窗口内词频统计匹配成功的单词数量窗口超出总长度时收缩左指针移除左侧单词保证窗口长度固定匹配数等于基准词频的种类数时记录左指针为有效起始索引4.5 结果返回遍历结束后返回存储所有有效起始索引的结果数组。五、测试用例逐行推演示例1推演s “barfoothefoobarman”, words [“foo”,“bar”]核心参数word_len3word_cnt2total_len6基准词频{“foo”:1, “bar”:1}分组遍历i0、1、2i0组右指针滑动截取bar、“foo”窗口匹配记录索引0后续滑动截取the、“foo”、“bar”窗口再次匹配记录索引9最终结果[0,9]示例2推演s “wordgoodgoodgoodbestword”, words [“word”,“good”,“best”,“word”]基准词频{“word”:2, “good”:1, “best”:1}字符串中仅含1个word无窗口能匹配词频结果为空数组六、边界情况全覆盖处理6.1 极端边界场景s长度等于串联子串长度直接判断整体是否匹配words仅含一个单词查找s中所有该单词的起始索引words含重复单词哈希表正常统计频次窗口严格匹配次数s中无有效子串返回空数组6.2 边界测试用例# 用例1单个单词 s aaa, words [a] → 输出[0,1,2] # 用例2s长度等于总长度 s abcdef, words [abc,def] → 输出[0] # 用例3无匹配子串 s abcd, words [ef] → 输出[]七、核心总结与拓展7.1 解题核心要点抓住固定单词长度利用题目“所有单词等长”的条件分组滑动窗口避免暴力枚举哈希表词频对比快速判断窗口内单词是否匹配解决重复单词和乱序匹配问题滑动窗口动态调整保证窗口长度固定实时维护词频时间复杂度最优7.2 同类题型拓展本题是滑动窗口哈希表的经典困难题适配场景字符串子串匹配问题词频统计与排列组合匹配固定长度/可变长度滑动窗口问题易错点提醒1. 忘记按单词长度分组导致超时2. 未处理words中重复单词词频统计错误3. 窗口收缩时匹配数更新错误导致结果漏判或多判。原创不易觉得有用的话欢迎点赞、收藏、关注后续持续更新LeetCode高频题解、滑动窗口/哈希表技巧和面试真题解析
