<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看