<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智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 0211. 添加與搜索單詞 \* 數據結構設計 ## 題目地址(211. 添加與搜索單詞 - 數據結構設計) <https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/> ## 題目描述 ``` <pre class="calibre18">``` 請你設計一個數據結構,支持 添加新單詞 和 查找字符串是否與任何先前添加的字符串匹配 。 實現詞典類 WordDictionary : WordDictionary() 初始化詞典對象 void addWord(word) 將 word 添加到數據結構中,之后可以對它進行匹配 bool search(word) 如果數據結構中存在字符串與 word 匹配,則返回 true ;否則,返回 false 。word 中可能包含一些 '.' ,每個 . 都可以表示任何一個字母。 示例: 輸入: ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] 輸出: [null,null,null,null,false,true,true,true] 解釋: WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True 提示: 1 <= word.length <= 500 addWord 中的 word 由小寫英文字母組成 search 中的 word 由 '.' 或小寫英文字母組成 最調用多 50000 次 addWord 和 search ``` ``` ## 前置知識 - 前綴樹 ## 公司 - 阿里 - 騰訊 ## 思路 我們首先不考慮字符"."的情況。這種情況比較簡單,我們 addWord 直接添加到數組尾部,search 則線性查找即可。 接下來我們考慮特殊字符“.”,其實也不難,只不過 search 的時候,判斷如果是“.”, 我們認為匹配到了,繼續往后匹配即可。 上面的代碼復雜度會比較高,我們考慮優化。如果你熟悉前綴樹的話,應該注意到這可以使用前綴樹來進行優化。前綴樹優化之后每次查找復雜度是O(h)O(h)O(h), 其中 h 是前綴樹深度,也就是最長的字符串長度。 關于前綴樹,LeetCode 有很多題目。有的是直接考察,讓你實現一個前綴樹,有的是間接考察,比如本題。前綴樹代碼見下方,大家之后可以直接當成前綴樹的解題模板使用。 ![](https://img.kancloud.cn/34/0c/340c37fc6c68e2b73809d19d20a78a96_827x602.jpg) 由于我們這道題需要考慮特殊字符".",因此我們需要對標準前綴樹做一點改造,insert 不做改變,我們只需要改變 search 即可,代碼(Python 3): ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Returns if the word is in the trie. :type word: str :rtype: bool """</span> curr = self.Trie <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-string">'.'</span>: wizards = [] <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> curr.keys(): <span class="hljs-keyword">if</span> k == <span class="hljs-string">'#'</span>: <span class="hljs-keyword">continue</span> wizards.append(self.search(word[:i] + k + word[i + <span class="hljs-params">1</span>:])) <span class="hljs-keyword">return</span> any(wizards) <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> <span class="hljs-keyword">False</span> curr = curr[w] <span class="hljs-keyword">return</span> <span class="hljs-string">"#"</span> <span class="hljs-keyword">in</span> curr ``` ``` 標準的前綴樹搜索我也貼一下代碼,大家可以對比一下: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Returns if the word is in the trie. :type word: str :rtype: bool """</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: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> curr = curr[w] <span class="hljs-keyword">return</span> <span class="hljs-string">"#"</span> <span class="hljs-keyword">in</span> curr ``` ``` ## 關鍵點 - 前綴樹(也叫字典樹),英文名 Trie(讀作 tree 或者 try) ## 代碼 - 語言支持:Python3 Python3 Code: 關于 Trie 的代碼: ``` <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> <span class="hljs-string">""" Initialize your data structure here. """</span> self.Trie = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Inserts a word into the trie. :type word: str :rtype: void """</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">search</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Returns if the word is in the trie. :type word: str :rtype: bool """</span> curr = self.Trie <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-string">'.'</span>: wizards = [] <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> curr.keys(): <span class="hljs-keyword">if</span> k == <span class="hljs-string">'#'</span>: <span class="hljs-keyword">continue</span> wizards.append(self.search(word[:i] + k + word[i + <span class="hljs-params">1</span>:])) <span class="hljs-keyword">return</span> any(wizards) <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> <span class="hljs-keyword">False</span> curr = curr[w] <span class="hljs-keyword">return</span> <span class="hljs-string">"#"</span> <span class="hljs-keyword">in</span> curr ``` ``` 主邏輯代碼: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">WordDictionary</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> <span class="hljs-string">""" Initialize your data structure here. """</span> self.trie = Trie() <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">addWord</span><span class="hljs-params">(self, word: str)</span> -> <span class="hljs-keyword">None</span>:</span> <span class="hljs-string">""" Adds a word into the data structure. """</span> self.trie.insert(word) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self, word: str)</span> -> bool:</span> <span class="hljs-string">""" Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. """</span> <span class="hljs-keyword">return</span> self.trie.search(word) <span class="hljs-title"># Your WordDictionary object will be instantiated and called as such:</span> <span class="hljs-title"># obj = WordDictionary()</span> <span class="hljs-title"># obj.addWord(word)</span> <span class="hljs-title"># param_2 = obj.search(word)</span> ``` ``` ## 相關題目 - [0208.implement-trie-prefix-tree](208.implement-trie-prefix-tree.html) - [0212.word-search-ii](212.word-search-ii.html) - [0472.concatenated-words](problems/472.concatenated-words.md) - [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md)
                  <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>

                              哎呀哎呀视频在线观看