本次刷题日记的第 75篇，力扣题为：30. 串联所有单词的子串，困难
一、题目描述：
串联所有单词的子串，看上去好像又是一个涉及到查找的题目，我们来看看如何去解决吧
😁😁😁
二、这道题考察了什么思想？你的思路是什么？
串联所有单词的子串 题目都给我们提出了哪些要求，看看我们是否能清楚的知道需要做成什么样：
- 题目给出了一个字符串 s，和一个字符串数组 words
- 题目要求我们使用 words 中所有字符串各种组合方式，再 s 中去匹配是否能匹配上子串，如果可以则找到匹配字符串的起始位置
- 题目还透露出信息，s 字符串中的单词长度 和 words 中的单词长度保持一致
分析
看到这道题我们需要如何下手呢？
很容易想到的一个情况就是暴力求解，将 words 中的单词，各种排列组合后得到一个列表，通过遍历 s 字符串，逐个去匹配列表中的单词组合，如果匹配的上，则记录起点位置到结果数组中
例如这样：
上述这种情况，应该很容易是可以想到的，但是我们仔细查看模拟的过程之后，我们可以发现其实在过程中，我们做了大量的重复比对，耗时耗力
我们可以思考一下如何减少这些重复的比对，
例如上述，我们是否可以按照单词的维度来进行偏移，这样子的话，我们就可以按照一个单词的长度进行移动了
那么向这样，我们还需要用 words 中组合出来的列表逐个去匹配吗？
为了提高效率，其实我们可以是用 hash 表 的方式 来记录从某个起始位置开始到结束为止，是否包含 words 中的字符串 1 次，如果都是包含的 1 次，那么就满足条件，并将起始位置加入到结果集中
看到这里，其实还不够，因为此处的情况，是一定是按照确实是完整单词来偏移的，仔细看，我们漏掉了一些情况，例如
仅仅是对于当前示例来说，不存在从单词内部为起始位置仍然也符合条件的情况，但我们不排除有这种情况的组合：words=["obo", "bob"]
这么看来，剩下的就是来实现我们的想法了
- 按照单词宽度的维度来遍历字符串 s
- 如果 s 的某个起始位置对应的前 lenW 单词都是满足条件的（都是 words 中，且出现 1 次），那么就将起始位置加入到结果集，如果不满足，则去掉之前的偏移记录，从下一个单词的起始位置开始遍历和计数
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
编码如下：
// 使用滑动窗口的方式 func findSubstring(s string, words []string) []int { // 校验基本参数边界 lenS, lenW, wordLength := len(s), len(words), len(words[0]) if lenW < 1 { return []int{} } if lenS < wordLength*lenW { return []int{} } help := map[string]int{} for _, word := range words { help[word]++ } // 开始滑动窗口 var res []int for i := 0; i < wordLength; i++ { cntMap := map[string]int{} cnt := 0 // 开始遍历 s 字符串，按照单词的宽度进行滑动 for start, j := i, i; j <= lenS-wordLength; j += wordLength { curWord := s[j : j+wordLength] if num, isFound := help[curWord]; isFound { for cntMap[curWord] >= num { cntMap[s[start:start+wordLength]]-- cnt-- start += wordLength } cntMap[curWord]++ cnt++ } else { for start < j { cntMap[s[start:start+wordLength]]-- cnt-- start += wordLength } start += wordLength } if cnt == lenW { res = append(res, start) } } } return res }
四、总结：
按照我们这种使用滑动窗口的实现方式，时间复杂度我们可以仔细看看，是 O(wordLength * lenS) ，因为我们需要遍历 wordLength 次 的 S 字符串，每一次都会将 S 字符串遍历完毕
那么空间复杂度是多少呢？
我们可以仔细看看咱们开辟空间的位置，每一次遍历 S 字符串的时候都会开辟一个哈希表来帮我们计数，因此空间复杂度是 O(wordLength * lenW) ， 是其中上述字符代表的含义和编码中实现的字符含义一致
wordLength ：一个单词的长度
lenW：words 数组的长度
lenS：s 字符串的长度
原题地址：30. 串联所有单词的子串
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
