{"id":843,"date":"2021-03-05T15:24:40","date_gmt":"2021-03-05T07:24:40","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=843"},"modified":"2021-03-05T16:45:12","modified_gmt":"2021-03-05T08:45:12","slug":"leetcode-211","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/03\/05\/leetcode-211\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 211 &#8211; Add and Search Word"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"843\" class=\"elementor elementor-843\">\n\t\t\t\t\t\t<div class=\"elementor-inner\">\n\t\t\t\t<div class=\"elementor-section-wrap\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-43549ab elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"43549ab\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4cc9a48\" data-id=\"4cc9a48\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4cb6208 elementor-widget elementor-widget-text-editor\" data-id=\"4cb6208\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-text-editor elementor-clearfix\">\n\t\t\t\t<h4><span style=\"text-decoration: underline;\"><strong>\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4><p class=\"md-end-block md-p\"><span class=\"md-plain\">Design a data structure that supports adding new words and finding if a string matches any previously added string.<\/span><\/p><p class=\"md-end-block md-p\"><span class=\"md-plain\">Implement the <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>WordDictionary<\/code><\/span><span class=\"md-plain\"> class:<\/span><\/p><ul class=\"ul-list\" data-mark=\"-\"><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-pair-s\" spellcheck=\"false\"><code>WordDictionary()<\/code><\/span><span class=\"md-plain\"> Initializes the object.<\/span><\/p><\/li><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-pair-s\" spellcheck=\"false\"><code>void addWord(word)<\/code><\/span><span class=\"md-plain\"> Adds <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>word<\/code><\/span><span class=\"md-plain\"> to the data structure, it can be matched later.<\/span><\/p><\/li><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-pair-s\" spellcheck=\"false\"><code>bool search(word)<\/code><\/span><span class=\"md-plain\"> Returns <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>true<\/code><\/span><span class=\"md-plain\"> if there is any string in the data structure that matches <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>word<\/code><\/span><span class=\"md-plain\"> or <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>false<\/code><\/span><span class=\"md-plain\"> otherwise. <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>word<\/code><\/span><span class=\"md-plain\"> may contain dots <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>'.'<\/code><\/span><span class=\"md-plain\"> where dots can be matched with any letter.<\/span><\/p><\/li><\/ul><p class=\"md-end-block md-p\">\u00a0<\/p><p class=\"md-end-block md-p\"><span class=\"md-pair-s \"><strong><span class=\"md-plain\">Example:<\/span><\/strong><\/span><\/p><pre class=\"md-fences md-end-block ty-contain-cm modeLoaded\" lang=\"\" spellcheck=\"false\"><span role=\"presentation\">Input<\/span><br \/><span role=\"presentation\">[\"WordDictionary\",\"addWord\",\"addWord\",\"addWord\",\"search\",\"search\",\"search\",\"search\"]<\/span><br \/><span role=\"presentation\">[[],[\"bad\"],[\"dad\"],[\"mad\"],[\"pad\"],[\"bad\"],[\".ad\"],[\"b..\"]]<\/span><br \/><span role=\"presentation\">Output<\/span><br \/><span role=\"presentation\">[null,null,null,null,false,true,true,true]<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\">Explanation<\/span><br \/><span role=\"presentation\">WordDictionary wordDictionary = new WordDictionary();<\/span><br \/><span role=\"presentation\">wordDictionary.addWord(\"bad\");<\/span><br \/><span role=\"presentation\">wordDictionary.addWord(\"dad\");<\/span><br \/><span role=\"presentation\">wordDictionary.addWord(\"mad\");<\/span><br \/><span role=\"presentation\">wordDictionary.search(\"pad\"); \/\/ return False<\/span><br \/><span role=\"presentation\">wordDictionary.search(\"bad\"); \/\/ return True<\/span><br \/><span role=\"presentation\">wordDictionary.search(\".ad\"); \/\/ return True<\/span><br \/><span role=\"presentation\">wordDictionary.search(\"b..\"); \/\/ return True<\/span><\/pre><p class=\"md-end-block md-p\">\u00a0<\/p><p class=\"md-end-block md-p\"><span class=\"md-pair-s \"><strong><span class=\"md-plain\">Constraints:<\/span><\/strong><\/span><\/p><ul class=\"ul-list\" data-mark=\"-\"><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-pair-s\" spellcheck=\"false\"><code>1 &lt;= word.length &lt;= 500<\/code><\/span><\/p><\/li><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-pair-s\" spellcheck=\"false\"><code>word<\/code><\/span><span class=\"md-plain\"> in <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>addWord<\/code><\/span><span class=\"md-plain\"> consists lower-case English letters.<\/span><\/p><\/li><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-pair-s\" spellcheck=\"false\"><code>word<\/code><\/span><span class=\"md-plain\"> in <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>search<\/code><\/span><span class=\"md-plain\"> consist of <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>'.'<\/code><\/span><span class=\"md-plain\"> or lower-case English letters.<\/span><\/p><\/li><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-plain\">At most <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>50000<\/code><\/span><span class=\"md-plain\"> calls will be made to <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>addWord<\/code><\/span><span class=\"md-plain\"> and <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>search<\/code><\/span><span class=\"md-plain\">.<\/span><\/p><\/li><\/ul>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a6e28da elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a6e28da\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1fa6485\" data-id=\"1fa6485\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c52112f elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"c52112f\" data-element_type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ab1716e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ab1716e\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9d0831e\" data-id=\"9d0831e\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7440128 elementor-widget elementor-widget-text-editor\" data-id=\"7440128\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-text-editor elementor-clearfix\">\n\t\t\t\t<h4><span style=\"text-decoration: underline;\"><strong>\u4e00\u5237\u984c\u89e3\uff08Trie\uff09\uff1a<\/strong><\/span><\/h4><p>\u00a0 \u00a0 \u00a0 \u00a0 \u9019\u984c\u6574\u984c\u5be6\u73fe\u4e0a\u8207\u4e00\u822c\u7684\u5b57\u9996\u6a39\u6c92\u751a\u9ebc\u5340\u5225\uff0cAdd\u4e5f\u662f\u7167\u6a23\u7684\u904d\u6b77\u5b57\u7b26\u4e32\u6bcf\u500b\u5b57\u7b26\uff0c\u4f9d\u6b21\u52a0\u5230\u5b57\u9996\u6a39\u4e2d\uff1b\u4e00\u822c\u5b57\u7b26\u7684Search\u4e5f\u662f\u901a\u904e\u904d\u6b77\u5b57\u9996\u6a39\u4e2d\u5c0d\u61c9\u7684\u5b57\u6bcd\u5b50\u7bc0\u9ede\u9032\u884c\u6aa2\u67e5\u3002\u6bd4\u8f03\u7279\u6b8a\u7684\u662f\uff0c\u9019\u984c\u5bb9\u8a31\u8f38\u5165&#8217;.&#8217;\uff0c\u4ee3\u8868\u300c\u4efb\u610f\u5b57\u6bcd\u300d\u3002<\/p><p>\u00a0 \u00a0 \u00a0 \u00a0 \u9019\u5c31\u4ee3\u8868\u6211\u5011\u5728\u904d\u6b77\u904e\u7a0b\u4e2d\uff0c\u6bcf\u9047\u5230\u4e00\u6b21&#8217;.&#8217;\uff0c\u90fd\u8981\u5c0d26\u500b\u5b50\u7bc0\u9ede\u4e0b\u5404\u81ea\u7684\u6240\u6709\u5b50\u7bc0\u9ede\u9032\u884c\u6aa2\u67e5\u3002\u9019\u6a23\u4e00\u4f86\uff0c\u5e38\u898f\u7684\u5728Search\u65b9\u6cd5\u88e1\u904d\u6b77\u5c31\u7121\u6cd5\u6eff\u8db3\u9700\u6c42\u4e86\uff0c\u6211\u5011\u9700\u8981\u901a\u904e\u5229\u7528\u905e\u6b78\u9032\u884c\u6df1\u5ea6\u512a\u5148\u67e5\u627e\u53bb\u5f97\u5230\u6211\u5011\u7684\u7d50\u679c\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8022296 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8022296\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3fce56a\" data-id=\"3fce56a\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9acc604 elementor-widget elementor-widget-text-editor\" data-id=\"9acc604\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-text-editor elementor-clearfix\">\n\t\t\t\t<pre class=\"md-fences md-end-block ty-contain-cm modeLoaded\" lang=\"c#\" spellcheck=\"false\"><span role=\"presentation\"><span class=\"cm-keyword\">public<\/span> <span class=\"cm-keyword\">class<\/span> <span class=\"cm-def\">WordDictionary<\/span> {<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-variable\">TrieNode<\/span> <span class=\"cm-variable\">root<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-variable-3\">bool<\/span> <span class=\"cm-variable\">canFound<\/span>;<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable\">WordDictionary<\/span>()<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">root<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-keyword\">new<\/span> <span class=\"cm-variable\">TrieNode<\/span>();<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">canFound<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-atom\">false<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0  }<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-keyword\">void<\/span> <span class=\"cm-variable\">AddWord<\/span>(<span class=\"cm-variable-3\">string<\/span> <span class=\"cm-variable\">word<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">TrieNode<\/span> <span class=\"cm-variable\">curr<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">root<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">foreach<\/span> (<span class=\"cm-variable-3\">char<\/span> <span class=\"cm-variable\">c<\/span> <span class=\"cm-keyword\">in<\/span> <span class=\"cm-variable\">word<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">curr<\/span>.<span class=\"cm-variable\">children<\/span>[<span class=\"cm-variable\">c<\/span> <span class=\"cm-operator\">-<\/span> <span class=\"cm-string\">'a'<\/span>] <span class=\"cm-operator\">==<\/span> <span class=\"cm-atom\">null<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">curr<\/span>.<span class=\"cm-variable\">children<\/span>[<span class=\"cm-variable\">c<\/span> <span class=\"cm-operator\">-<\/span> <span class=\"cm-string\">'a'<\/span>] <span class=\"cm-operator\">=<\/span> <span class=\"cm-keyword\">new<\/span> <span class=\"cm-variable\">TrieNode<\/span>();<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">curr<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">curr<\/span>.<span class=\"cm-variable\">children<\/span>[<span class=\"cm-variable\">c<\/span> <span class=\"cm-operator\">-<\/span> <span class=\"cm-string\">'a'<\/span>];<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">curr<\/span>.<span class=\"cm-variable\">isWordEnd<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-atom\">true<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0  }<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable-3\">bool<\/span> <span class=\"cm-variable\">Search<\/span>(<span class=\"cm-variable-3\">string<\/span> <span class=\"cm-variable\">word<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">TrieNode<\/span> <span class=\"cm-variable\">curr<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">root<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">canFound<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-atom\">false<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">SearchHelper<\/span>(<span class=\"cm-variable\">curr<\/span>, <span class=\"cm-variable\">word<\/span>, <span class=\"cm-number\">0<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span> <span class=\"cm-variable\">canFound<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0  }<br \/><\/span><br \/>    \/\/\u905e\u6b78\u67e5\u627e<br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">void<\/span> <span class=\"cm-variable\">SearchHelper<\/span>(<span class=\"cm-variable\">TrieNode<\/span> <span class=\"cm-variable\">node<\/span>, <span class=\"cm-variable-3\">string<\/span> <span class=\"cm-variable\">word<\/span>, <span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">idx<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span> (<span class=\"cm-variable\">canFound<\/span> <span class=\"cm-operator\">||<\/span> <span class=\"cm-variable\">node<\/span> <span class=\"cm-operator\">==<\/span> <span class=\"cm-atom\">null<\/span>) { <span class=\"cm-keyword\">return<\/span>; }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span> (<span class=\"cm-variable\">word<\/span>.<span class=\"cm-variable\">Length<\/span> <span class=\"cm-operator\">==<\/span> <span class=\"cm-variable\">idx<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">isWordEnd<\/span>) { <span class=\"cm-variable\">canFound<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-atom\">true<\/span>; }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\">\u200b        \/\/\u9047\u5230'.'\u7684\u5b57\u7b26\u6642\uff0c\u9700\u8981\u5c0d26\u500b\u5b50\u7bc0\u9ede\u9032\u884c\u6aa2\u67e5<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">word<\/span>[<span class=\"cm-variable\">idx<\/span>] <span class=\"cm-operator\">==<\/span> <span class=\"cm-string\">'.'<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">for<\/span> (<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">i<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-string\">'a'<\/span>; <span class=\"cm-variable\">i<\/span> <span class=\"cm-operator\">&lt;=<\/span> <span class=\"cm-string\">'z'<\/span>; <span class=\"cm-variable\">i<\/span><span class=\"cm-operator\">++<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">SearchHelper<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">children<\/span>[<span class=\"cm-variable\">i<\/span> <span class=\"cm-operator\">-<\/span> <span class=\"cm-string\">'a'<\/span>], <span class=\"cm-variable\">word<\/span>, <span class=\"cm-variable\">idx<\/span><span class=\"cm-operator\">+<\/span><span class=\"cm-number\">1<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">else<\/span><\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">SearchHelper<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">children<\/span>[<span class=\"cm-variable\">word<\/span>[<span class=\"cm-variable\">idx<\/span>] <span class=\"cm-operator\">-<\/span> <span class=\"cm-string\">'a'<\/span>], <span class=\"cm-variable\">word<\/span>, <span class=\"cm-variable\">idx<\/span><span class=\"cm-operator\">+<\/span><span class=\"cm-number\">1<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\"> \u00a0  }<\/span><br \/><span role=\"presentation\">}<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"><span class=\"cm-keyword\">public<\/span> <span class=\"cm-keyword\">class<\/span> <span class=\"cm-def\">TrieNode<\/span><\/span><br \/><span role=\"presentation\">{<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable\">TrieNode<\/span>[] <span class=\"cm-variable\">children<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-keyword\">new<\/span> <span class=\"cm-variable\">TrieNode<\/span>[<span class=\"cm-number\">26<\/span>];<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable-3\">bool<\/span> <span class=\"cm-variable\">isWordEnd<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable\">TrieNode<\/span>()<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">isWordEnd<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-atom\">false<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0  }<\/span><br \/><span role=\"presentation\">}<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>\u984c\u76ee\u63cf\u8ff0\uff1a Design a data structure that supports adding new  &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/lonelinerd.com\/index.php\/2021\/03\/05\/leetcode-211\/\"> <span class=\"screen-reader-text\">[LeetCode\u5237\u984c\u7b46\u8a18] 211 &#8211; Add and Search Word<\/span> Read More &raquo;<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-843","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/843","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=843"}],"version-history":[{"count":8,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/843\/revisions"}],"predecessor-version":[{"id":852,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/843\/revisions\/852"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=843"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=843"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=843"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}