<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>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0472. 連接詞 ## 題目地址(472. 連接詞) <https://leetcode-cn.com/problems/concatenated-words/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個不含重復單詞的列表,編寫一個程序,返回給定單詞列表中所有的連接詞。 連接詞的定義為:一個字符串完全是由至少兩個給定數組中的單詞組成的。 示例: 輸入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] 輸出: ["catsdogcats","dogcatsdog","ratcatdogcat"] 解釋: "catsdogcats"由"cats", "dog" 和 "cats"組成; "dogcatsdog"由"dog", "cats"和"dog"組成; "ratcatdogcat"由"rat", "cat", "dog"和"cat"組成。 說明: 給定數組的元素總數不超過 10000。 給定數組中元素的長度總和不超過 600000。 所有輸入字符串只包含小寫字母。 不需要考慮答案輸出的順序。 ``` ``` ## 前置知識 - 前綴樹 ## 公司 - 阿里 - 字節 ## 思路 本題我的思路是直接使用前綴樹來解決。**標準的前綴樹模板**我在之前的題解中提到了,感興趣的可以到下方的相關題目中查看。 這道題這里我們不需要 search,我們的做法是: - 先進行一次遍歷,將 words 全部插入(insert)到前綴樹中。 - 然后再進行一次遍歷,查找每一個單詞有幾個單詞表中的單詞組成 - 如果大于 2,則將其加入到 res 中 - 最后返回 res 即可 我們構造的前綴樹大概是這樣的: ![](https://img.kancloud.cn/70/ef/70ef583cfd039447946d697507ee3f37_1312x1080.jpg) 問題的關鍵在于第二步中的**查找每一個單詞有幾個單詞表中的單詞組成**。 其實如果你了解前綴樹的話應該不難寫出來。 比如查找 catsdogcats: - 我們先從 c 到 a 到 t,發現 t 是單詞結尾,我們數量 + 1 - 然后將剩下的部分“sdogcats”重新執行上述過程。 - s 發現找不到,我們返回 0 - 因此最終結果是 1 很明顯這個邏輯是錯誤的,正確的劃分應該是: - 我們先從 c 到 a 到 t,再到 s,此時數量 + 1 - 然后將剩下的“dogcats”重復上述過程 - dog 找到了,數量 + 1 - 最后將 cats 加入。也找到了,數量再加 1 由于我們并不知道 cat 這里斷開,結果更大?還是 cats 這里斷開結果更大?因此我們的做法是將其全部遞歸求出,然后取出最大值即可。如果我們直接這樣遞歸的話,可能會超時,卡在最后一個測試用例上。一個簡單的方式是記憶化遞歸,從而避免重復計算,經測試這種方法能夠通過。 ## 代碼 代碼支持:Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Trie</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span> self.Trie = {} self.visited = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, word)</span>:</span> curr = self.Trie <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> word: <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: curr[w] = {} curr = curr[w] curr[<span class="hljs-string">'#'</span>] = <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cntWords</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> word: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> word <span class="hljs-keyword">in</span> self.visited: <span class="hljs-keyword">return</span> self.visited[word] curr = self.Trie res = float(<span class="hljs-string">'-inf'</span>) <span class="hljs-keyword">for</span> i, w <span class="hljs-keyword">in</span> enumerate(word): <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: <span class="hljs-keyword">return</span> res curr = curr[w] <span class="hljs-keyword">if</span> <span class="hljs-string">'#'</span> <span class="hljs-keyword">in</span> curr: res = max(res, <span class="hljs-params">1</span> + self.cntWords(word[i + <span class="hljs-params">1</span>:])) self.visited[word] = res <span class="hljs-keyword">return</span> res <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">findAllConcatenatedWordsInADict</span><span class="hljs-params">(self, words: List[str])</span> -> List[str]:</span> self.trie = Trie() res = [] <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> words: self.trie.insert(word) <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> words: <span class="hljs-keyword">if</span> self.trie.cntWords(word) >= <span class="hljs-params">2</span>: res.append(word) <span class="hljs-keyword">return</span> res ``` ``` ## 關鍵點分析 - 前綴樹 ## 相關題目 - [0208.implement-trie-prefix-tree](https://github.com/azl397985856/leetcode/blob/b8e8fa5f0554926efa9039495b25ed7fc158372a/problems/208.implement-trie-prefix-tree.md) - [0211.add-and-search-word-data-structure-design](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/211.add-and-search-word-data-structure-design.md) - [0212.word-search-ii](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/212.word-search-ii.md) - [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md) - [1032.stream-of-characters](https://github.com/azl397985856/leetcode/blob/master/problems/1032.stream-of-characters.md) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 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>

                              哎呀哎呀视频在线观看