<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國際加速解決方案。 廣告
                # 0208. 實現 Trie (前綴樹) ## 題目地址(208. 實現 Trie (前綴樹)) <https://leetcode-cn.com/problems/implement-trie-prefix-tree/> ## 題目描述 ``` <pre class="calibre18">``` 實現一個 Trie (前綴樹),包含 insert, search, 和 startsWith 這三個操作。 示例: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true 說明: 你可以假設所有的輸入都是由小寫字母 a-z 構成的。 保證所有輸入均為非空字符串。 ``` ``` ## 前置知識 - 前綴樹 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一道很直接的題目,上來就讓你實現`前綴樹(字典樹)`。這算是基礎數據結構中的 知識了,不清楚什么是字典樹的可以查閱相關資料。 我們看到題目給出的使用方法`new Trie`, `insert`,`search`和`startWith`. 為了區分`search`和`startWith`我們需要增加一個標示來區分當前節點是否是某個單詞的結尾。 因此節點的數據結構應該是: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">TrieNode</span>(<span class="hljs-params">val</span>) </span>{ <span class="hljs-keyword">this</span>.val = val; <span class="hljs-title">// 當前的字母</span> <span class="hljs-keyword">this</span>.children = []; <span class="hljs-title">// 題目要求字典僅有a-z,那么其長度最大為26(26個字母)</span> <span class="hljs-keyword">this</span>.isWord = <span class="hljs-params">false</span>; } ``` ``` 每次 insert 我們其實都是從根節點出發,一個一個找到我們需要添加的節點,修改 children 的值. 我們應該修改哪一個 child 呢? 我們需要一個函數來計算索引 ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">computeIndex</span>(<span class="hljs-params">c</span>) </span>{ <span class="hljs-keyword">return</span> c.charCodeAt(<span class="hljs-params">0</span>) - <span class="hljs-string">"a"</span>.charCodeAt(<span class="hljs-params">0</span>); } ``` ``` 其實不管 insert, search 和 startWith 的邏輯都是差不多的,都是從 root 出發, 找到我們需要操作的 child, 然后進行相應操作(添加,修改,返回)。 ![](https://img.kancloud.cn/08/e0/08e038e4c5e4db4840ad43b89c7ddde5_827x602.jpg) ## 關鍵點解析 - 前綴樹 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=208 lang=javascript * * [208] Implement Trie (Prefix Tree) * * https://leetcode.com/problems/implement-trie-prefix-tree/description/ * * algorithms * Medium (36.93%) * Total Accepted: 172K * Total Submissions: 455.5K * Testcase Example: '["Trie","insert","search","search","startsWith","insert","search"]\n[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]' * * Implement a trie with insert, search, and startsWith methods. * * Example: * * * Trie trie = new Trie(); * * trie.insert("apple"); * trie.search("apple"); // returns true * trie.search("app"); // returns false * trie.startsWith("app"); // returns true * trie.insert("app"); * trie.search("app"); // returns true * * * Note: * * * You may assume that all inputs are consist of lowercase letters a-z. * All inputs are guaranteed to be non-empty strings. * * */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">TrieNode</span>(<span class="hljs-params">val</span>) </span>{ <span class="hljs-keyword">this</span>.val = val; <span class="hljs-keyword">this</span>.children = []; <span class="hljs-keyword">this</span>.isWord = <span class="hljs-params">false</span>; } <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">computeIndex</span>(<span class="hljs-params">c</span>) </span>{ <span class="hljs-keyword">return</span> c.charCodeAt(<span class="hljs-params">0</span>) - <span class="hljs-string">"a"</span>.charCodeAt(<span class="hljs-params">0</span>); } <span class="hljs-title">/** * Initialize your data structure here. */</span> <span class="hljs-keyword">var</span> Trie = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">this</span>.root = <span class="hljs-keyword">new</span> TrieNode(<span class="hljs-params">null</span>); }; <span class="hljs-title">/** * Inserts a word into the trie. * @param {string} word * @return {void} */</span> Trie.prototype.insert = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">word</span>) </span>{ <span class="hljs-keyword">let</span> ws = <span class="hljs-keyword">this</span>.root; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < word.length; i++) { <span class="hljs-keyword">const</span> c = word[i]; <span class="hljs-keyword">const</span> current = computeIndex(c); <span class="hljs-keyword">if</span> (!ws.children[current]) { ws.children[current] = <span class="hljs-keyword">new</span> TrieNode(c); } ws = ws.children[current]; } ws.isWord = <span class="hljs-params">true</span>; }; <span class="hljs-title">/** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */</span> Trie.prototype.search = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">word</span>) </span>{ <span class="hljs-keyword">let</span> ws = <span class="hljs-keyword">this</span>.root; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < word.length; i++) { <span class="hljs-keyword">const</span> c = word[i]; <span class="hljs-keyword">const</span> current = computeIndex(c); <span class="hljs-keyword">if</span> (!ws.children[current]) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; ws = ws.children[current]; } <span class="hljs-keyword">return</span> ws.isWord; }; <span class="hljs-title">/** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix * @return {boolean} */</span> Trie.prototype.startsWith = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">prefix</span>) </span>{ <span class="hljs-keyword">let</span> ws = <span class="hljs-keyword">this</span>.root; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < prefix.length; i++) { <span class="hljs-keyword">const</span> c = prefix[i]; <span class="hljs-keyword">const</span> current = computeIndex(c); <span class="hljs-keyword">if</span> (!ws.children[current]) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; ws = ws.children[current]; } <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; }; <span class="hljs-title">/** * Your Trie object will be instantiated and called as such: * var obj = new Trie() * obj.insert(word) * var param_2 = obj.search(word) * var param_3 = obj.startsWith(prefix) */</span> ``` ``` ## 相關題目 - [0211.add-and-search-word-data-structure-design](211.add-and-search-word-data-structure-design.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) - [1032.stream-of-characters](https://github.com/azl397985856/leetcode/blob/master/problems/1032.stream-of-characters.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>

                              哎呀哎呀视频在线观看