# 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。