# 0030. 串联所有单词的子串 ## 题目地址（30. 串联所有单词的子串） <https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 示例 1： 输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。 示例 2： 输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[] ``` ``` ## 前置知识 - 字符串 - 数组 - 哈希表 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路 本题是要我们找出 words 中`所有单词按照任意顺序串联`形成的单词中恰好出现在 s 中的索引，因此顺序是不重要的。换句话说，我们只要统计每一个单词的出现情况即可。以题目中 s = "barfoothefoobarman", words = \["foo","bar"\] 为例。 我们只需要统计 foo 出现了一次，bar 出现了一次即可。我们只需要在 s 中找到同样包含一次 foo 和一次 bar 的子串即可。由于 words 中的字符串都是等长的，因此编码上也会比较简单。 1. 我们的目标状态是 Counter(words)，即对 words 进行一次计数。 2. 我们只需从头开始遍历一次数组，每次截取 word 长度的字符，一共截取 words 长度次即可。 3. 如果我们截取的 Counter 和 Counter(words)一致，则加入到 res 4. 否则我们继续一个指针，继续执行步骤二 5. 重复执行这个逻辑直到达到数组尾部 ## 关键点解析 - Counter ## 代码 - 语言支持：Python3 ``` <pre class="calibre18">``` <span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> Counter <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findSubstring</span><span class="hljs-params">(self, s: str, words: List[str])</span> -> List[int]:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> words: <span class="hljs-keyword">return</span> [] res = [] n = len(words) word_len = len(words[<span class="hljs-params">0</span>]) window_len = word_len * n target = Counter(words) i = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i < len(s) - window_len + <span class="hljs-params">1</span>: sliced = [] start = i <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n): sliced.append(s[start:start + word_len]) start += word_len <span class="hljs-keyword">if</span> Counter(sliced) == target: res.append(i) i += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> res ``` ``` **复杂度分析** 其中 N 为 words 中的总字符数。 - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。