{"id":1876,"date":"2016-03-14T14:56:47","date_gmt":"2016-03-14T06:56:47","guid":{"rendered":"http:\/\/boweihe.me\/?p=1876"},"modified":"2016-03-14T14:56:47","modified_gmt":"2016-03-14T06:56:47","slug":"leetcode-208-implement-trie-prefix-tree","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1876","title":{"rendered":"LeetCode 208. Implement Trie (Prefix Tree)"},"content":{"rendered":"

\u9898\u76ee\uff1a<\/strong>https:\/\/leetcode.com\/problems\/implement-trie-prefix-tree\/
\n\u601d\u8def\uff1a<\/strong>
\n\u524d\u7f00\u6811\u7684\u6982\u5ff5\uff0c\u53c2\u8003\u8fd9\u91cc<\/a>\u3002\u8c37\u6b4c\u641c\u5230\u7684\uff0c\u5176\u5b9e\u6709\u4e00\u5927\u628a~
\n\u5224\u65ad\u662f\u5426\u6709\u8fd9\u4e48\u4e2a\u201c\u513f\u5b50\u201d\u7684\u65f6\u5019\uff0c\u589e\u52a0\u4e86\u4e00\u4e2ahasEnd\u5e03\u5c14\u503c\uff0c\u5982\u679c\u6709\u4ee5\u8fd9\u4e2a\u70b9\u4e3a\u7ed3\u675f\u7684\u5b57\u7b26\u5219\u8bbe\u7f6e\u6210true.
\n\u9650\u5236\uff1a\u4e3a\u4e86\u5b9e\u73b0\u65b9\u4fbf\uff0c\u73b0\u5728\u53ea\u80fd\u5b58\u50a8a-z\u517126\u4e2a\u5b57\u7b26\uff0c\u5982\u679c\u518d\u6269\u5c55\u53ef\u4ee5\u8003\u8651\u7528map\u6765\u5b58\u5b57\u7b26\u5bf9\u5e94\u7684\u5b69\u5b50\u6307\u9488\u3002
\n\u5355\u8bcd\u7684\u5b57\u7b26\u6570\u91cf\u4e3aM\uff0c\u63d2\u5165\u8282\u70b9\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(M)
\nstartWith(..)\u548csearch(..)\u4e00\u5927\u534a\u90e8\u5206\u53ef\u4ee5\u5408\u5e76
\n\u4ee3\u7801\uff1a<\/strong><\/p>\n

class TrieNode {\npublic:\n\tbool hasEnd;\n\tTrieNode** children;\n\t\/\/ Initialize your data structure here.\n\tTrieNode() {\n\t\tchildren = NULL;\n\t\thasEnd = false;\n\t}\n\tbool hasChild(char c) {\n\t\tif (NULL == children)\n\t\t\treturn false;\n\t\treturn !(NULL == children[c - 'a']);\n\t}\n\tTrieNode* addChild(char c) {\n\t\tif (NULL == children) {\n\t\t\tchildren = new TrieNode*[26];\n\t\t\tfor (int i = 0; i<26; i++)\n\t\t\t\tchildren[i] = NULL;\n\t\t}\n\t\tint pos = c - 'a';\n\t\tchildren[pos] = new TrieNode;\n\t\treturn children[pos];\n\t}\n};\nclass Trie {\npublic:\n\tTrie() {\n\t\troot = new TrieNode();\n\t}\n\t\/\/ Inserts a word into the trie.\n\tvoid insert(string word) {\n\t\tint wordSz = word.size();\n\t\tchar c;\n\t\tTrieNode *currNode = root;\n\t\tfor (int i = 0; i<wordSz; i++) {\n\t\t\tc = word[i];\n\t\t\tif (currNode->hasChild(c))\n\t\t\t\tcurrNode = currNode->children[c - 'a'];\n\t\t\telse {\n\t\t\t\tcurrNode = currNode->addChild(c);\n\t\t\t}\n\t\t\tif (i == wordSz - 1)\n\t\t\t\tcurrNode->hasEnd = true;\n\t\t}\n\t}\n\t\/\/ Returns if the word is in the trie.\n\tbool search(string word) {\n\t\tint wordSz = word.size();\n\t\tchar c;\n\t\tTrieNode *currNode = root;\n\t\tfor (int i = 0; i<wordSz; i++) {\n\t\t\tc = word[i];\n\t\t\tif (currNode->hasChild(c))\n\t\t\t\tcurrNode = currNode->children[c - 'a'];\n\t\t\telse\n\t\t\t\treturn false;\n\t\t}\n\t\treturn currNode->hasEnd;\n\t}\n\t\/\/ Returns if there is any word in the trie\n\t\/\/ that starts with the given prefix.\n\tbool startsWith(string prefix) {\n\t\tint wordSz = prefix.size();\n\t\tchar c;\n\t\tTrieNode *currNode = root;\n\t\tfor (int i = 0; i<wordSz; i++) {\n\t\t\tc = prefix[i];\n\t\t\tif (currNode->hasChild(c))\n\t\t\t\tcurrNode = currNode->children[c - 'a'];\n\t\t\telse\n\t\t\t\treturn false;\n\t\t}\n\t\treturn true;\n\t}\nprivate:\n\tTrieNode* root;\n};\n\/\/ Your Trie object will be instantiated and called as such:\n\/\/ Trie trie;\n\/\/ trie.insert(\"somestring\");\n\/\/ trie.search(\"key\");<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\uff1ahttps:\/\/leetcode.com\/problems\/implement-trie-prefix-tree\/ \u601d\u8def\uff1a \u524d\u7f00\u6811\u7684\u6982\u5ff5\uff0c\u53c2\u8003\u8fd9\u91cc\u3002\u8c37\u6b4c\u641c\u5230\u7684\uff0c\u5176\u5b9e\u6709\u4e00\u5927\u628a~ \u5224\u65ad\u662f\u5426\u6709\u8fd9\u4e48\u4e2a\u201c\u513f\u5b50\u201d\u7684\u65f6\u5019\uff0c\u589e\u52a0\u4e86\u4e00\u4e2ahasEnd\u5e03\u5c14\u503c\uff0c\u5982\u679c\u6709\u4ee5\u8fd9\u4e2a\u70b9\u4e3a\u7ed3\u675f\u7684\u5b57\u7b26\u5219\u8bbe\u7f6e\u6210true. \u9650\u5236\uff1a\u4e3a\u4e86\u5b9e\u73b0\u65b9\u4fbf\uff0c\u73b0\u5728\u53ea\u80fd\u5b58\u50a8a-z\u517126\u4e2a\u5b57\u7b26\uff0c\u5982\u679c\u518d\u6269\u5c55\u53ef\u4ee5\u8003\u8651\u7528map\u6765\u5b58\u5b57\u7b26\u5bf9\u5e94\u7684\u5b69\u5b50\u6307\u9488\u3002 \u5355\u8bcd\u7684\u5b57\u7b26\u6570\u91cf\u4e3aM\uff0c\u63d2\u5165\u8282\u70b9\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(M) startWith(..)\u548csearch(..)\u4e00\u5927\u534a\u90e8\u5206\u53ef\u4ee5\u5408\u5e76 \u4ee3\u7801\uff1a class TrieNode { public: bool hasEnd; TrieNode** children; \/\/ Initialize your data structure here. TrieNode() { children = NULL; hasEnd = false; } bool hasChild(char c) { if (NULL == children) return false; return !(NULL == children[c – ‘a’]); } TrieNode* addChild(char c) { if (NULL == […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-1876","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1876","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1876"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1876\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1876"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1876"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1876"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}