LeetCode-Go 题解精讲第 30 题 Substring with Concatenation of All Words 的滑动窗口与计数映射实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 30 题Substring with Concatenation of All Words串联所有单词的子串以 leetcode/0030.Substring-with-Concatenation-of-All-Words/README.md 为骨架深入讲解 LeetCode-Go 仓库中该题的官方 Go 解法。你将掌握如何利用「单词定长 必须连续拼接」两个限定条件把看似复杂的全排列匹配问题简化为哈希计数 定长窗口扫描并理解findSubstring、checkWords、copyMap三个函数的实际调用关系与边界处理最终可以独立完成此类字符串匹配题并跑通仓库自带的单元测试。一、题目原文与示例You are given a string,s, and a list of words,words, that are all of the same length. Find all starting indices of substring(s) insthat is a concatenation of each word inwordsexactly once and without any intervening characters.即给定一个源字符串s和一个单词数组words数组中所有单词长度相同找出s中所有「恰好由words中每个单词各出现一次、且单词之间无任何间隔字符连续拼接而成」的子串的起始下标。Example 1Input: s barfoothefoobarman, words [foo,bar] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are barfoor and foobar respectively. The output order does not matter, returning [9,0] is fine too.Example 2Input: s wordgoodgoodgoodbestword, words [word,good,best,word] Output: []Example 2 值得特别留意words中存在重复单词word两次意味着目标子串中word也必须恰好出现两次而源字符串中word只出现一次因此结果为空。这印证了「每个单词各出现一次含重复计数」这一约束在实现中必须通过计数而非去重集合来落实。二、题目大意给定一个源字符串s再给一个字符串数组要求在源字符串中找到由字符串数组各种组合组成的连续串的起始下标如果存在多个在结果中都需要输出。三、解题思路两个关键限定条件这一题看似很难但是有 2 个限定条件也导致这题不是特别难字符串数组里面的字符串长度都是一样的——这使我们可以把源字符串按固定长度length切成等宽的单词块来匹配而不是做任意长度的子串穷举要求字符串数组中的字符串都要连续连在一起的前后顺序可以是任意排列组合——这意味着我们不需要枚举全排列只需要验证「一段连续区域内每个单词的出现次数恰好等于words中的要求次数」即可。基于此原文档给出的核心思路是先将字符串数组里面的所有字符串都存到map中并累计出现的次数然后从源字符串头开始扫描每次判断字符串数组里面的字符串是否全部都用完了计数是否为 0如果全部都用完了并且长度正好是字符串数组任意排列组合的总长度就记录下这个组合的起始下标如果不符合就继续考察源字符串的下一个字符直到扫完整个源字符串。四、Go 源码实现与逐段精解仓库中的实现位于 leetcode/0030.Substring-with-Concatenation-of-All-Words/30. Substring with Concatenation of All Words.go完整代码如下package leetcode func findSubstring(s string, words []string) []int { if len(words) 0 { return []int{} } res : []int{} counter : map[string]int{} for _, w : range words { counter[w] } length, totalLen, tmpCounter : len(words[0]), len(words[0])*len(words), copyMap(counter) for i, start : 0, 0; i len(s)-length1 start len(s)-length1; i { //fmt.Printf(sub %v i %v lenght %v start %v tmpCounter %v totalLen %v\n, s[i:ilength], i, length, start, tmpCounter, totalLen) if tmpCounter[s[i:ilength]] 0 { tmpCounter[s[i:ilength]]-- //fmt.Printf(******sub %v i %v lenght %v start %v tmpCounter %v totalLen %v\n, s[i:ilength], i, length, start, tmpCounter, totalLen) if checkWords(tmpCounter) (ilength-start totalLen) { res append(res, start) continue } i i length - 1 } else { start i start - 1 tmpCounter copyMap(counter) } } return res } func checkWords(s map[string]int) bool { flag : true for _, v : range s { if v 0 { flag false break } } return flag } func copyMap(s map[string]int) map[string]int { c : map[string]int{} for k, v : range s { c[k] v } return c }4.1 三个函数的分工findSubstring(s string, words []string) []int主函数。空words直接返回空切片对应测试用例{n, []string{}}否则构建需求计数表并执行滑动扫描。checkWords(s map[string]int) bool判断计数表中是否所有键的计数都已经降到 0。只有全部为 0才说明当前窗口恰好用完了每个单词。copyMap(s map[string]int) map[string]int深拷贝计数表。因为每次从新起点start重新匹配时都要把计数表恢复为原始需求值直接复用同一个 map 会因递减操作污染数据因此必须拷贝。4.2 关键状态变量变量含义示例sbarfoothefoobarman, words[foo,bar]counter每个单词的需求次数基准计数表{foo:1, bar:1}length单词长度即len(words[0])3totalLen目标子串总长度即len(words[0])*len(words)6tmpCounter当前窗口的剩余需求计数初始为counter的深拷贝随扫描递减i当前扫描到的单词块起始位置0, 3, 6, …start当前候选窗口的起点0, 1, 2, …4.3 主循环逻辑拆解外层循环的条件是i len(s)-length1 start len(s)-length1保证取子串s[i:ilength]不越界。循环体内分两种分支分支一当前单词块命中需求tmpCounter[s[i:ilength]] 0说明s[i:ilength]属于需要的单词执行tmpCounter[s[i:ilength]]-- if checkWords(tmpCounter) (ilength-start totalLen) { res append(res, start) continue } i i length - 1先递减对应计数若checkWords(tmpCounter)为真所有单词都用完且ilength-start totalLen窗口总长恰好等于totalLen则start就是一个合法起始下标记录后continue否则i i length - 1配合循环末尾的i实现一次前进length个字节——即从当前窗口直接跳到下一个单词块这正是利用定长单词这一限定条件的核心优化。分支二当前单词块不命中需求tmpCounter[s[i:ilength]] 0为假说明从当前start出发的窗口已经不可能成立必须换起点start i start - 1 tmpCounter copyMap(counter)起点右移一位i回到start-1配合i让下一次循环从新起点重新开始扫描计数表重置为原始需求深拷贝重新开始统计。4.4 为什么需要双重条件判断checkWords(tmpCounter)负责单词全部用完ilength-start totalLen负责窗口长度达标。二者缺一不可前者保证每个单词恰好出现一次计数降到 0后者保证窗口没有越界拼接、没有把多余字符算进来。只有两者同时满足才把start记入结果。五、测试用例与运行验证仓库为该题提供了 11 组测试用例位于 leetcode/0030.Substring-with-Concatenation-of-All-Words/30. Substring with Concatenation of All Words_test.go覆盖了常规匹配、重复单词、单单词、边界与失败场景输入s输入words期望输出考察点aaaaaaaa[aa,aa,aa][0,1,2]大量重复单词窗口逐位滑动barfoothefoobarman[foo,bar][0,9]题目示例 1wordgoodgoodgoodbestword[word,good,best,word][]题目示例 2重复单词不可满足goodgoodgoodgoodgood[good][0,4,8,12,16]单词长度大于 1 时的逐位滑动barofoothefoolbarman[foo,bar][]字符被打散无法拼接bbarffoothefoobarman[foo,bar][]前导干扰字符ooroodoofoodtoo[foo,doo,roo,tee,oo][]存在不在词表内的块abc[a,b,c][0]单词长度为 1a[b][]单字符不匹配ab[ba][]单词拼接顺序不符n[][]空单词数组空输入保护测试驱动方式为表驱动测试para30结构体承载输入one为源字符串、two为单词数组ans30承载期望答案Test_Problem30遍历所有用例并打印输入输出对照。这符合仓库统一的题解测试风格。在仓库根目录执行项目自带的测试脚本 gotest.sh内部运行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...或直接对单目录执行go test -v ./leetcode/0030.Substring-with-Concatenation-of-All-Words/即可看到该用例被逐一验证通过。仓库go.mod声明的 Go 版本为 1.19测试时请使用兼容的 Go 工具链。六、复杂度分析与延伸思考时间复杂度主循环在最坏情况下对s的每个起始位置重新扫描每次扫描约消耗len(words)个单词块总代价近似O(len(s) × len(words))checkWords每次遍历计数表键的数量不超过words去重后的个数。相比对words做全排列O(k!)级别的朴素思路本解法的哈希计数方案是质变的优化。空间复杂度counter与tmpCounter存储去重后的单词计数空间为O(去重单词数)另有结果切片res的开销。可以推断本实现还有进一步优化的空间例如引入单词长度length的模分组、复用滑动窗口而不是每次回退start重新扫描这也是滑动窗口类题目的常见进阶方向例如仓库中 0076.Minimum-Window-Substring、0438.Find-All-Anagrams-in-a-String 等题目使用的都是同一类计数 窗口思想读者可以横向对比加深理解。七、小结本题是定长单词 连续拼接约束下的典型字符串匹配题。核心套路可总结为三步用map[string]int统计words中每个单词的需求次数从源字符串逐位或逐块扫描命中需求则递减计数并前进一个单词长度不命中则移动起点并重置计数当剩余计数全部归零且窗口长度恰为totalLen时记录起点。掌握这一套路后凡是由若干定长子串任意排列组成的匹配类问题都可以用同样的哈希计数框架快速求解。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：第 30 题 Substring with Concatenation of All Words 的滑动窗口与计数映射实现
LeetCode-Go 题解精讲第 30 题 Substring with Concatenation of All Words 的滑动窗口与计数映射实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 30 题Substring with Concatenation of All Words串联所有单词的子串以 leetcode/0030.Substring-with-Concatenation-of-All-Words/README.md 为骨架深入讲解 LeetCode-Go 仓库中该题的官方 Go 解法。你将掌握如何利用「单词定长 必须连续拼接」两个限定条件把看似复杂的全排列匹配问题简化为哈希计数 定长窗口扫描并理解findSubstring、checkWords、copyMap三个函数的实际调用关系与边界处理最终可以独立完成此类字符串匹配题并跑通仓库自带的单元测试。一、题目原文与示例You are given a string,s, and a list of words,words, that are all of the same length. Find all starting indices of substring(s) insthat is a concatenation of each word inwordsexactly once and without any intervening characters.即给定一个源字符串s和一个单词数组words数组中所有单词长度相同找出s中所有「恰好由words中每个单词各出现一次、且单词之间无任何间隔字符连续拼接而成」的子串的起始下标。Example 1Input: s barfoothefoobarman, words [foo,bar] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are barfoor and foobar respectively. The output order does not matter, returning [9,0] is fine too.Example 2Input: s wordgoodgoodgoodbestword, words [word,good,best,word] Output: []Example 2 值得特别留意words中存在重复单词word两次意味着目标子串中word也必须恰好出现两次而源字符串中word只出现一次因此结果为空。这印证了「每个单词各出现一次含重复计数」这一约束在实现中必须通过计数而非去重集合来落实。二、题目大意给定一个源字符串s再给一个字符串数组要求在源字符串中找到由字符串数组各种组合组成的连续串的起始下标如果存在多个在结果中都需要输出。三、解题思路两个关键限定条件这一题看似很难但是有 2 个限定条件也导致这题不是特别难字符串数组里面的字符串长度都是一样的——这使我们可以把源字符串按固定长度length切成等宽的单词块来匹配而不是做任意长度的子串穷举要求字符串数组中的字符串都要连续连在一起的前后顺序可以是任意排列组合——这意味着我们不需要枚举全排列只需要验证「一段连续区域内每个单词的出现次数恰好等于words中的要求次数」即可。基于此原文档给出的核心思路是先将字符串数组里面的所有字符串都存到map中并累计出现的次数然后从源字符串头开始扫描每次判断字符串数组里面的字符串是否全部都用完了计数是否为 0如果全部都用完了并且长度正好是字符串数组任意排列组合的总长度就记录下这个组合的起始下标如果不符合就继续考察源字符串的下一个字符直到扫完整个源字符串。四、Go 源码实现与逐段精解仓库中的实现位于 leetcode/0030.Substring-with-Concatenation-of-All-Words/30. Substring with Concatenation of All Words.go完整代码如下package leetcode func findSubstring(s string, words []string) []int { if len(words) 0 { return []int{} } res : []int{} counter : map[string]int{} for _, w : range words { counter[w] } length, totalLen, tmpCounter : len(words[0]), len(words[0])*len(words), copyMap(counter) for i, start : 0, 0; i len(s)-length1 start len(s)-length1; i { //fmt.Printf(sub %v i %v lenght %v start %v tmpCounter %v totalLen %v\n, s[i:ilength], i, length, start, tmpCounter, totalLen) if tmpCounter[s[i:ilength]] 0 { tmpCounter[s[i:ilength]]-- //fmt.Printf(******sub %v i %v lenght %v start %v tmpCounter %v totalLen %v\n, s[i:ilength], i, length, start, tmpCounter, totalLen) if checkWords(tmpCounter) (ilength-start totalLen) { res append(res, start) continue } i i length - 1 } else { start i start - 1 tmpCounter copyMap(counter) } } return res } func checkWords(s map[string]int) bool { flag : true for _, v : range s { if v 0 { flag false break } } return flag } func copyMap(s map[string]int) map[string]int { c : map[string]int{} for k, v : range s { c[k] v } return c }4.1 三个函数的分工findSubstring(s string, words []string) []int主函数。空words直接返回空切片对应测试用例{n, []string{}}否则构建需求计数表并执行滑动扫描。checkWords(s map[string]int) bool判断计数表中是否所有键的计数都已经降到 0。只有全部为 0才说明当前窗口恰好用完了每个单词。copyMap(s map[string]int) map[string]int深拷贝计数表。因为每次从新起点start重新匹配时都要把计数表恢复为原始需求值直接复用同一个 map 会因递减操作污染数据因此必须拷贝。4.2 关键状态变量变量含义示例sbarfoothefoobarman, words[foo,bar]counter每个单词的需求次数基准计数表{foo:1, bar:1}length单词长度即len(words[0])3totalLen目标子串总长度即len(words[0])*len(words)6tmpCounter当前窗口的剩余需求计数初始为counter的深拷贝随扫描递减i当前扫描到的单词块起始位置0, 3, 6, …start当前候选窗口的起点0, 1, 2, …4.3 主循环逻辑拆解外层循环的条件是i len(s)-length1 start len(s)-length1保证取子串s[i:ilength]不越界。循环体内分两种分支分支一当前单词块命中需求tmpCounter[s[i:ilength]] 0说明s[i:ilength]属于需要的单词执行tmpCounter[s[i:ilength]]-- if checkWords(tmpCounter) (ilength-start totalLen) { res append(res, start) continue } i i length - 1先递减对应计数若checkWords(tmpCounter)为真所有单词都用完且ilength-start totalLen窗口总长恰好等于totalLen则start就是一个合法起始下标记录后continue否则i i length - 1配合循环末尾的i实现一次前进length个字节——即从当前窗口直接跳到下一个单词块这正是利用定长单词这一限定条件的核心优化。分支二当前单词块不命中需求tmpCounter[s[i:ilength]] 0为假说明从当前start出发的窗口已经不可能成立必须换起点start i start - 1 tmpCounter copyMap(counter)起点右移一位i回到start-1配合i让下一次循环从新起点重新开始扫描计数表重置为原始需求深拷贝重新开始统计。4.4 为什么需要双重条件判断checkWords(tmpCounter)负责单词全部用完ilength-start totalLen负责窗口长度达标。二者缺一不可前者保证每个单词恰好出现一次计数降到 0后者保证窗口没有越界拼接、没有把多余字符算进来。只有两者同时满足才把start记入结果。五、测试用例与运行验证仓库为该题提供了 11 组测试用例位于 leetcode/0030.Substring-with-Concatenation-of-All-Words/30. Substring with Concatenation of All Words_test.go覆盖了常规匹配、重复单词、单单词、边界与失败场景输入s输入words期望输出考察点aaaaaaaa[aa,aa,aa][0,1,2]大量重复单词窗口逐位滑动barfoothefoobarman[foo,bar][0,9]题目示例 1wordgoodgoodgoodbestword[word,good,best,word][]题目示例 2重复单词不可满足goodgoodgoodgoodgood[good][0,4,8,12,16]单词长度大于 1 时的逐位滑动barofoothefoolbarman[foo,bar][]字符被打散无法拼接bbarffoothefoobarman[foo,bar][]前导干扰字符ooroodoofoodtoo[foo,doo,roo,tee,oo][]存在不在词表内的块abc[a,b,c][0]单词长度为 1a[b][]单字符不匹配ab[ba][]单词拼接顺序不符n[][]空单词数组空输入保护测试驱动方式为表驱动测试para30结构体承载输入one为源字符串、two为单词数组ans30承载期望答案Test_Problem30遍历所有用例并打印输入输出对照。这符合仓库统一的题解测试风格。在仓库根目录执行项目自带的测试脚本 gotest.sh内部运行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...或直接对单目录执行go test -v ./leetcode/0030.Substring-with-Concatenation-of-All-Words/即可看到该用例被逐一验证通过。仓库go.mod声明的 Go 版本为 1.19测试时请使用兼容的 Go 工具链。六、复杂度分析与延伸思考时间复杂度主循环在最坏情况下对s的每个起始位置重新扫描每次扫描约消耗len(words)个单词块总代价近似O(len(s) × len(words))checkWords每次遍历计数表键的数量不超过words去重后的个数。相比对words做全排列O(k!)级别的朴素思路本解法的哈希计数方案是质变的优化。空间复杂度counter与tmpCounter存储去重后的单词计数空间为O(去重单词数)另有结果切片res的开销。可以推断本实现还有进一步优化的空间例如引入单词长度length的模分组、复用滑动窗口而不是每次回退start重新扫描这也是滑动窗口类题目的常见进阶方向例如仓库中 0076.Minimum-Window-Substring、0438.Find-All-Anagrams-in-a-String 等题目使用的都是同一类计数 窗口思想读者可以横向对比加深理解。七、小结本题是定长单词 连续拼接约束下的典型字符串匹配题。核心套路可总结为三步用map[string]int统计words中每个单词的需求次数从源字符串逐位或逐块扫描命中需求则递减计数并前进一个单词长度不命中则移动起点并重置计数当剩余计数全部归零且窗口长度恰为totalLen时记录起点。掌握这一套路后凡是由若干定长子串任意排列组成的匹配类问题都可以用同样的哈希计数框架快速求解。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考