{"id":440,"date":"2017-09-27T22:23:38","date_gmt":"2017-09-28T05:23:38","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=440"},"modified":"2018-04-19T08:27:46","modified_gmt":"2018-04-19T15:27:46","slug":"leetcode-208-implement-trie-prefix-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-208-implement-trie-prefix-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 208. Implement Trie (Prefix Tree)"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 208. Implement Trie (Prefix Tree) - \u5237\u9898\u627e\u5de5\u4f5c EP73\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/f48wGD-MuQw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Implement a trie with\u00a0<code>insert<\/code>,\u00a0<code>search<\/code>, and\u00a0<code>startsWith<\/code>\u00a0methods.<\/p>\n<p><b>Note:<\/b><br \/>\nYou may assume that all inputs are consist of lowercase letters\u00a0<code>a-z<\/code>.<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\"\n     style=\"display:block; text-align:center;\"\n     data-ad-layout=\"in-article\"\n     data-ad-format=\"fluid\"\n     data-ad-client=\"ca-pub-2404451723245401\"\n     data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><br \/>\nTree\/children array<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-445\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-444\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/208-ep74-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ \/ Array<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua \r\n\/\/ Running time: 99 ms\r\nclass Trie {\r\npublic:\r\n    \/** Initialize your data structure here. *\/\r\n    Trie(): root_(new TrieNode()) {}\r\n    \r\n    \/** Inserts a word into the trie. *\/\r\n    void insert(const string&amp; word) {\r\n        TrieNode* p = root_.get();\r\n        for (const char c : word) {\r\n            if (!p-&gt;children[c - 'a'])\r\n                p-&gt;children[c - 'a'] = new TrieNode();\r\n            p = p-&gt;children[c - 'a'];\r\n        }\r\n        p-&gt;is_word = true;\r\n    }\r\n    \r\n    \/** Returns if the word is in the trie. *\/\r\n    bool search(const string&amp; word) const {\r\n        const TrieNode* p = find(word);\r\n        return p &amp;&amp; p-&gt;is_word;\r\n    }\r\n    \r\n    \/** Returns if there is any word in the trie that starts with the given prefix. *\/\r\n    bool startsWith(const string&amp; prefix) const {\r\n        return find(prefix) != nullptr;\r\n    }\r\nprivate:\r\n    struct TrieNode {\r\n        TrieNode():is_word(false), children(26, nullptr){}\r\n        \r\n        ~TrieNode() {\r\n            for (TrieNode* child : children)\r\n                if (child) delete child;\r\n        }\r\n               \r\n        bool is_word;\r\n        vector&lt;TrieNode*&gt; children;\r\n    };\r\n    \r\n    const TrieNode* find(const string&amp; prefix) const {\r\n        const TrieNode* p = root_.get();\r\n        for (const char c : prefix) {\r\n            p = p-&gt;children[c - 'a'];\r\n            if (p == nullptr) break;\r\n        }\r\n        return p;\r\n    }\r\n    \r\n    std::unique_ptr&lt;TrieNode&gt; root_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ hashmap<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 98 ms\r\nclass Trie {\r\npublic:\r\n    \/** Initialize your data structure here. *\/\r\n    Trie(): root_(new TrieNode()) {}\r\n    \r\n    \/** Inserts a word into the trie. *\/\r\n    void insert(const string&amp; word) {\r\n        TrieNode* p = root_.get();\r\n        for (const char c : word) {\r\n            if (!p-&gt;children.count(c))\r\n                p-&gt;children[c] = new TrieNode();\r\n            p = p-&gt;children[c];\r\n        }\r\n        p-&gt;is_word = true;\r\n    }\r\n    \r\n    \/** Returns if the word is in the trie. *\/\r\n    bool search(const string&amp; word) const {\r\n        const TrieNode* p = find(word);\r\n        return p &amp;&amp; p-&gt;is_word;\r\n    }\r\n    \r\n    \/** Returns if there is any word in the trie that starts with the given prefix. *\/\r\n    bool startsWith(const string&amp; prefix) const {\r\n        return find(prefix) != nullptr;\r\n    }\r\nprivate:\r\n    struct TrieNode {\r\n        TrieNode():is_word(false){}\r\n        \r\n        ~TrieNode() {\r\n            for (auto&amp; kv : children)\r\n                if (kv.second) delete kv.second;\r\n        }\r\n        \r\n        bool is_word;\r\n        unordered_map&lt;char, TrieNode*&gt; children;\r\n    };\r\n    \r\n    const TrieNode* find(const string&amp; prefix) const {\r\n        const TrieNode* p = root_.get();\r\n        for (const char c : prefix) {\r\n            if (!p-&gt;children.count(c)) return nullptr;\r\n            p = p-&gt;children.at(c);\r\n        }\r\n        return p;\r\n    }\r\n    \r\n    std::unique_ptr&lt;TrieNode&gt; root_;\r\n};\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 184 ms\r\nclass Trie {\r\n    class TrieNode {\r\n        public TrieNode() {\r\n            children = new TrieNode[26];\r\n            is_word = false;\r\n        }\r\n        public boolean is_word;\r\n        public TrieNode[] children;\r\n    }\r\n    \r\n    private TrieNode root;\r\n    \r\n    \/** Initialize your data structure here. *\/\r\n    public Trie() {\r\n        root = new TrieNode();\r\n    }\r\n    \r\n    \/** Inserts a word into the trie. *\/\r\n    public void insert(String word) {\r\n        TrieNode p = root;\r\n        for (int i = 0; i &lt; word.length(); i++) {\r\n            int index = (int)(word.charAt(i) - 'a');\r\n            if (p.children[index] == null)\r\n                p.children[index] = new TrieNode();\r\n            p = p.children[index];\r\n        }\r\n        p.is_word = true;\r\n    }\r\n    \r\n    \/** Returns if the word is in the trie. *\/\r\n    public boolean search(String word) {\r\n        TrieNode node = find(word);\r\n        return node != null &amp;&amp; node.is_word;\r\n    }\r\n    \r\n    \/** Returns if there is any word in the trie that starts with the given prefix. *\/\r\n    public boolean startsWith(String prefix) {\r\n        TrieNode node = find(prefix);\r\n        return node != null;\r\n    }\r\n    \r\n    private TrieNode find(String prefix) {\r\n        TrieNode p = root;\r\n        for(int i = 0; i &lt; prefix.length(); i++) {\r\n            int index = (int)(prefix.charAt(i) - 'a');\r\n            if (p.children[index] == null) return null;\r\n            p = p.children[index];\r\n        }\r\n        return p;\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>Python 1:<\/p>\n<pre class=\"lang:python decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 469 ms\r\n\"\"\"\r\nclass Trie(object):\r\n    class TrieNode(object):\r\n        def __init__(self):\r\n            self.is_word = False\r\n            self.children = [None] * 26\r\n        \r\n    def __init__(self):\r\n        self.root = Trie.TrieNode()\r\n        \r\n\r\n    def insert(self, word):\r\n        p = self.root\r\n        for c in word:\r\n            index = ord(c) - ord('a')\r\n            if not p.children[index]: \r\n                p.children[index] = Trie.TrieNode()\r\n            p = p.children[index]\r\n        p.is_word = True\r\n\r\n    def search(self, word):\r\n        node = self.find(word)\r\n        return node is not None and node.is_word\r\n        \r\n\r\n    def startsWith(self, prefix):\r\n        return self.find(prefix) is not None\r\n    \r\n    def find(self, prefix):\r\n        p = self.root\r\n        for c in prefix:\r\n            index = ord(c) - ord('a')\r\n            if not p.children[index]: return None\r\n            p = p.children[index]\r\n        return p\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>Python 2:<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 212 ms\r\n\"\"\"\r\nclass Trie(object):            \r\n    def __init__(self):\r\n        self.root = {}\r\n        \r\n\r\n    def insert(self, word):\r\n        p = self.root\r\n        for c in word:            \r\n            if c not in p: \r\n                p[c] = {}\r\n            p = p[c]\r\n        p['#'] = True\r\n\r\n    def search(self, word):\r\n        node = self.find(word)\r\n        return node is not None and '#' in node\r\n        \r\n\r\n    def startsWith(self, prefix):\r\n        return self.find(prefix) is not None\r\n    \r\n    def find(self, prefix):\r\n        p = self.root\r\n        for c in prefix:            \r\n            if c not in p: return None\r\n            p = p[c]\r\n        return p<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Implement a trie with\u00a0insert,\u00a0search, and\u00a0startsWith\u00a0methods. Note: You may assume that all inputs are consist of lowercase letters\u00a0a-z. Idea: Tree\/children array &nbsp; &nbsp; Solution: C++&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[112,82,97,111,96],"class_list":["post-440","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-children","tag-hashtable","tag-prefix","tag-prefix-tree","tag-trie","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/440","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=440"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/440\/revisions"}],"predecessor-version":[{"id":2552,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/440\/revisions\/2552"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=440"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=440"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=440"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}