{"id":201704,"date":"2020-11-25T07:01:46","date_gmt":"2020-11-24T23:01:46","guid":{"rendered":"http:\/\/4563.org\/?p=201704"},"modified":"2020-11-25T07:01:46","modified_gmt":"2020-11-24T23:01:46","slug":"%e5%be%ae%e8%bd%af%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e5%ae%9e%e7%8e%b0-trie%ef%bc%88%e5%89%8d%e7%bc%80%e6%a0%91%ef%bc%89%ef%bc%8c%e6%9e%af%e7%87%a5%e8%87%b3%e6%9e%81%ef%bc%88%e6%bb%91%e7%a8%bd","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=201704","title":{"rendered":"\u5fae\u8f6f\u9762\u8bd5\u9898\uff1a\u5b9e\u73b0 Trie\uff08\u524d\u7f00\u6811\uff09\uff0c\u67af\u71e5\u81f3\u6781\uff08\u6ed1\u7a3d\uff09"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  \u5fae\u8f6f\u9762\u8bd5\u9898\uff1a\u5b9e\u73b0 Trie\uff08\u524d\u7f00\u6811\uff09\uff0c\u67af\u71e5\u81f3\u6781\uff08\u6ed1\u7a3d\uff09               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span>  <span><i><\/i> 5<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<p>\u5b9e\u73b0\u4e00\u4e2a Trie\uff0c\u5305\u542b insert, search, \u548c startsWith \u8fd9\u4e09\u4e2a\u65b9\u6cd5\u3002<\/p>\n<p>\u5728\u7ebf\u505a\u9898\u5730\u5740<\/p>\n<h2>\u6837\u4f8b 1:<\/h2>\n<pre><code>\u8f93\u5165:    insert(\"lintcode\")   search(\"lint\")   startsWith(\"lint\") \u8f93\u51fa:    false   true <\/code><\/pre>\n<h2>\u6837\u4f8b 2:<\/h2>\n<pre><code>\u8f93\u5165:   insert(\"lintcode\")   search(\"code\")   startsWith(\"lint\")   startsWith(\"linterror\")   insert(\"linterror\")   search(\"lintcode\u201d)   startsWith(\"linterror\") \u8f93\u51fa:    false   true   false   true   true <\/code><\/pre>\n<h2>\u9898\u89e3<\/h2>\n<p>Trie(\u524d\u7f00\u6811) \u7684\u6a21\u677f\u5e94\u7528.<\/p>\n<p>\u7ef4\u57fa\u767e\u79d1: https:\/\/zh.wikipedia.org\/zh-hans\/Trie<\/p>\n<pre><code>\/\/ Version 1: Array of TrieNodeclass TrieNode {     private TrieNode[] children;     public boolean hasWord;          public TrieNode() {         children = new TrieNode[26];         hasWord = false;     }          public void insert(String word, int index) {         if (index == word.length()) {             this.hasWord = true;             return;         }                  int pos = word.charAt(index) - 'a';         if (children[pos] == null) {             children[pos] = new TrieNode();         }         children[pos].insert(word, index + 1);     }          public TrieNode find(String word, int index) {         if (index == word.length()) {             return this;         }                  int pos = word.charAt(index) - 'a';         if (children[pos] == null) {             return null;         }         return children[pos].find(word, index + 1);     } } public class Trie {     private TrieNode root;      public Trie() {         root = new TrieNode();     }      \/\/ Inserts a word into the trie.     public void insert(String word) {         root.insert(word, 0);     }      \/\/ Returns if the word is in the trie.     public boolean search(String word) {         TrieNode node = root.find(word, 0);         return (node != null &amp;&amp; node.hasWord);     }      \/\/ Returns if there is any word in the trie     \/\/ that starts with the given prefix.     public boolean startsWith(String prefix) {         TrieNode node = root.find(prefix, 0);         return node != null;     } }  \/\/ Version 2: HashMap Version, this version will be TLE when you submit on LintCodeclass TrieNode {     \/\/ Initialize your data structure here.     char c;     HashMap&lt;Character, TrieNode&gt; children = new HashMap&lt;Character, TrieNode&gt;();     boolean hasWord;          public TrieNode(){              }          public TrieNode(char c){         this.c = c;     } } public class Trie {     private TrieNode root;      public Trie() {         root = new TrieNode();     }      \/\/ Inserts a word into the trie.     public void insert(String word) {         TrieNode cur = root;         HashMap&lt;Character, TrieNode&gt; curChildren = root.children;         char[] wordArray = word.toCharArray();         for(int i = 0; i &lt; wordArray.length; i++){             char wc = wordArray[i];             if(curChildren.containsKey(wc)){                 cur = curChildren.get(wc);             } else {                 TrieNode newNode = new TrieNode(wc);                 curChildren.put(wc, newNode);                 cur = newNode;             }             curChildren = cur.children;             if(i == wordArray.length - 1){                 cur.hasWord= true;             }         }     }      \/\/ Returns if the word is in the trie.     public boolean search(String word) {         if(searchWordNodePos(word) == null){             return false;         } else if(searchWordNodePos(word).hasWord)            return true;           else return false;     }      \/\/ Returns if there is any word in the trie     \/\/ that starts with the given prefix.     public boolean startsWith(String prefix) {         if(searchWordNodePos(prefix) == null){             return false;         } else return true;     }          public TrieNode searchWordNodePos(String s){         HashMap&lt;Character, TrieNode&gt; children = root.children;         TrieNode cur = null;         char[] sArray = s.toCharArray();         for(int i = 0; i &lt; sArray.length; i++){             char c = sArray[i];             if(children.containsKey(c)){                 cur = children.get(c);                 children = cur.children;             } else{                 return null;             }         }         return cur;     } } <\/code><\/pre>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>7<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li data-pid=\"4222440\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : learningman <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             \u4f1a\u4e86\uff0c\u90a3\u5fae\u8f6f\u8981\u6211\u5417                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4222441\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : xcai007 <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             \u67af\u71e5\u81f3\u6781!                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4222442\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : goodboy95 <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             \u6211\uff1a\u5b66\u4f1a\u4e86\uff0c\u9a6c\u4e0a\u53bb\u548c\u5fae\u8f6f\u5bf9\u7ebf\uff01<\/p>\n<p>\u51e0\u5929\u540e\uff0c\u5fae\u8f6f\u67d0\u529e\u516c\u5ba4\uff1a<br \/>\u6211\uff1a\u4f60\u597d\uff0c\u6211\u662f\u8fc7\u6765\u9762\u8bd5\u7684\u3002<br \/>\u9762\u8bd5\u5b98\uff1a\u597d\u7684\uff0c\u4f60\u770b\u770b\u4f60\u80fd\u4e0d\u80fd\u5199\u51fa\u4e2a\u5728\u5927\u91cf\u5b57\u7b26\u4e32\u4e2d\u8fdb\u884c\u5feb\u901f\u524d\u7f00\u5339\u914d\u7684\u65b9\u6cd5\uff0c\u8bed\u8a00\u968f\u610f\u3002<br \/>\u6211\uff1a\uff08 10 \u5206\u949f\u4e4b\u540e\uff09\u5199\u5b8c\u4e86\u3002<br \/>\u9762\u8bd5\u5b98\uff1a\u4e0d\u9519\u4e0d\u9519\uff0c\u90a3\u4e48\u95ee\u4e00\u4e0b\uff0c\u5982\u679c\u4e0d\u9650\u5b9a\u4ece\u524d\u7f00\u5339\u914d\u5b57\u7b26\u4e32\uff0c\u800c\u662f\u53ef\u4ee5\u4ece\u4e2d\u95f4\u5339\u914d\uff0c\u6bd4\u5982&#8221;cd&#8221;\u80fd\u5339\u914d&#8221;abcde&#8221;,\u90a3\u5e94\u8be5\u600e\u4e48\u529e\uff1f<br \/>\u6211\uff1a\uff08 WTF \uff1f\uff1f\uff09\u989d\u2026\u2026\u55ef\u2026\u2026\u90a3\u4e2a\u5565\u2026\u2026\u540e\u7f00\u6811\uff1f<br \/>\u9762\u8bd5\u5b98\uff1a\u597d\u7684\uff0c\u90a3\u4e48\u4f60\u80fd\u5b9e\u73b0\u4e00\u4e0b\u540e\u7f00\u6811\u5417\uff1f<br \/>\u6211\uff1a\uff08\u5fcd\u7740\u86cb\u75bc\u5199\u4e86\u4e2a\u628a\u4e00\u5806 trie \u6811\u7c98\u5728\u4e00\u8d77\u7684\u73a9\u610f\uff09<br \/>\u9762\u8bd5\u5b98\uff1a\u55ef\u2026\u2026\u884c\u5427\u3002\u90a3\u4e48\u628a\u521a\u521a\u7684\u95ee\u9898\u5012\u8fc7\u6765\uff0c\u5982\u679c\u73b0\u5728\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\u5e93\uff0c\u518d\u7ed9\u4f60\u4e00\u4e2a\u957f\u5b57\u7b26\u4e32\uff0c\u8981\u6c42\u4f60\u5feb\u901f\u627e\u51fa\u957f\u5b57\u7b26\u4e32\u5305\u542b\u5b57\u7b26\u4e32\u5e93\u7684\u54ea\u4e9b\u5143\u7d20\uff0c\u5e94\u8be5\u600e\u4e48\u529e\uff1f<br \/>\u6211\uff1a\uff08 wocao \uff1f\uff1f\uff1f\uff01\uff01\uff01\uff09\u989d\uff0c\u6211\u8bb0\u5f97\u597d\u50cf\u53ef\u4ee5\u7528 AC \u81ea\u52a8\u673a\u2026\u2026\u5427\u2026\u2026\uff08\u8349\u8349\u8349\uff0cAC \u81ea\u52a8\u673a\u4ee3\u7801\u548b\u5199\u6765\u7740\uff1f\u4ee5\u524d\u6ca1\u5199\u8fc7\u554a\uff09<br \/>\u9762\u8bd5\u5b98\uff1a\u5f88\u597d\uff0c\u7531\u4e8e\u65f6\u95f4\u5173\u7cfb\u5c31\u4e0d\u7528\u4f60\u5199\u51fa\u4ee3\u7801\u4e86\u3002<br \/>\u6211\uff1a\uff08\u547c\uff0c\u5e78\u597d\u9003\u8fc7\u4e00\u52ab\uff09<br \/>\u9762\u8bd5\u5b98\uff1a\u90a3\u4e48\uff0c\u6700\u540e\u518d\u95ee\u4e2a\u95ee\u9898\u3002\u521a\u521a\u8bf4\u7684\u5b57\u7b26\u4e32\u5e93\u5f53\u4e2d\uff0c\u5982\u679c\u6709\u90e8\u5206\u5b57\u7b26\u4e32\u662f\u5e26\u6709\u901a\u914d\u7b26\u7684\uff0c\u4f8b\u5982[&#8220;i*o&#8221;, &#8220;o?o&#8221;, &#8220;r?a*m&#8221;, &#8220;ft?&#8221;]\uff0c\u7136\u540e\u7ed9\u5b9a\u4e00\u4e2a\u666e\u901a\u7684\u957f\u5b57\u7b26\u4e32\uff0c\u4f8b\u5982&#8221;microsoft&#8221;\uff0c\u8fd9\u6837\u6211\u4eec\u8ba4\u4e3a&#8221;i*o&#8221;\u548c&#8221;o?o&#8221;\u5305\u542b\u5728&#8221;microsoft&#8221;\u91cc\u9762\uff0c\u800c&#8221;r?a*m&#8221;\u548c&#8221;ft?&#8221;\u4e0d\u5305\u542b\u3002\u90a3\u4e48\uff0c\u5982\u4f55\u624d\u80fd\u5feb\u901f\u627e\u51fa\u957f\u5b57\u7b26\u4e32\u91cc\u9762\u5305\u542b\u5b57\u7b26\u4e32\u5e93\u7684\u54ea\u4e9b\u5143\u7d20\u5462\uff1f<br \/>\u6211\uff1a\uff08\u4e24\u773c\u4e00\u9ed1\uff0c\u5012\u5728\u5730\u4e0a\uff09                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4222443\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : noreplay <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @goodboy95 \u6211\u5c31\u4e0d\u4e00\u6837\u4e86\u3002\u6211\u4f1a\u56e0\u4e3a\u5e74\u9f84\u5927\u4e86 \/\u7b2c\u4e00\u5b66\u5386\u4e0d\u597d \/\u6ca1\u6709\u4f4e\u5934\u6361\u5783\u573e\u7b49\u539f\u56e0\u6ca1\u53bb\u5bf9\u7ebf                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4222444\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : goodboy95 <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @noreplay \u8bf4\u8d77\u9762\u8bd5\u8fd9\u73a9\u610f\uff0c\u6211\u5c31\u60f3\u8d77\u6765\u90a3\u4e9b\u968f\u65f6\u53ef\u80fd\u51fa\u73b0\u7684\u53d8\u6001\u7b14\u8bd5\u9898\u3002\u4ee5\u524d\u8001\u4ee5\u4e3a\u53d8\u6001\u7b14\u8bd5\u9898\u53ea\u6709\u5927\u516c\u53f8\u4f1a\u51fa\uff0c\u50cf\u6211\u5728\u7684\u5c0f\u516c\u53f8\u53ea\u4f1a\u641e\u57fa\u7840\u9898\u3002\u540e\u6765\u6279\u5377\u5b50\u7684\u65f6\u5019\uff0c\u53d1\u73b0\u4e86\u4e00\u4efd\u5377\u5b50\u7684\u7f16\u7a0b\u9898\u662f\u4e8c\u7ef4\u52a8\u6001\u89c4\u5212+\u77e9\u9635\u5feb\u901f\u5e42\uff0c\u6211\u5f53\u573a\u5c31\u50bb\u4e86\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4222445\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : noreplay <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @goodboy95 \u62db\u7b97\u6cd5\u7684\u5417\uff1f\u5982\u679c\u53ea\u662f\u8f6f\u4ef6\u5c97\uff0c\u6211\u89c9\u5f97\u81ea\u5df1\u597d\u83dc\u597d\u83dc\u554a                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4222446\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : goodboy95 <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @noreplay \u5c31\u662f web \u5f00\u53d1\uff0c\u5230\u73b0\u5728\u6211\u90fd\u4e0d\u77e5\u9053\u662f\u54ea\u4e2a\u725b\u903c\u7684\u4e8c\u8d27\u628a\u90a3\u9053\u9898\u653e\u8fdb\u53bb\u7684\uff0c\u53cd\u6b63\u5e26\u8fd9\u9053\u9898\u7684\u5377\u5b50\uff0c\u522b\u8bf4\u77e9\u9635\u5feb\u901f\u5e42\u4e86\uff0c\u8fde\u4e8c\u7ef4\u52a8\u6001\u89c4\u5212\u6211\u90fd\u6ca1\u89c1\u8c01\u505a\u51fa\u6765\uff08\u867d\u7136\u6211\u4e0d\u770b\u7b54\u6848\u4e5f\u89e3\u4e0d\u51fa\u6765\u2026\u2026\uff09                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>\u5fae\u8f6f\u9762\u8bd5\u9898\uff1a\u5b9e\u73b0 Trie\uff08\u524d\u7f00\u6811&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201704"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=201704"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201704\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=201704"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=201704"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=201704"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}