{"id":227,"date":"2017-09-10T14:00:40","date_gmt":"2017-09-10T21:00:40","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=227"},"modified":"2018-07-10T18:54:26","modified_gmt":"2018-07-11T01:54:26","slug":"leetcode-676-implement-magic-dictionary","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-676-implement-magic-dictionary\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 676. Implement Magic Dictionary"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 676. Implement Magic Dictionary - \u5237\u9898\u627e\u5de5\u4f5c EP49\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/wq9XjoKMxek?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<div class=\"question-description\">\n<p>Implement a magic directory with\u00a0<code>buildDict<\/code>, and\u00a0<code>search<\/code>\u00a0methods.<\/p>\n<p>For the method\u00a0<code>buildDict<\/code>, you&#8217;ll be given a list of non-repetitive words to build a dictionary.<\/p>\n<p>For the method\u00a0<code>search<\/code>, you&#8217;ll be given a word, and judge whether if you modify\u00a0<b>exactly<\/b>\u00a0one character into\u00a0<b>another<\/b>\u00a0character in this word, the modified word is in the dictionary you just built.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre>Input: buildDict([\"hello\", \"leetcode\"]), Output: Null\r\nInput: search(\"hello\"), Output: False\r\nInput: search(\"hhllo\"), Output: True\r\nInput: search(\"hell\"), Output: False\r\nInput: search(\"leetcoded\"), Output: False\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>You may assume that all the inputs are consist of lowercase letters\u00a0<code>a-z<\/code>.<\/li>\n<li>For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.<\/li>\n<li>Please remember to\u00a0<b>RESET<\/b>\u00a0your class variables declared in class MagicDictionary, as static\/class variables are\u00a0<b>persisted across multiple test cases<\/b>. Please see\u00a0<a href=\"https:\/\/leetcode.com\/faq\/#different-output\">here<\/a>\u00a0for more details.<\/li>\n<\/ol>\n<\/div>\n<div id=\"interviewed-div\"><strong>Idea:<\/strong><\/div>\n<div><\/div>\n<div>Fuzzy match<\/div>\n<div><\/div>\n<div><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/676-ep49-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-231\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/676-ep49-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/676-ep49-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/676-ep49-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/676-ep49-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/676-ep49-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/div>\n<div><\/div>\n<div><strong>Time Complexity:<\/strong><\/div>\n<div>buildDict: O(n*m)<\/div>\n<div>n: numbers of words<\/div>\n<div>m: length of word<\/div>\n<div><\/div>\n<div>search: O(m)<\/div>\n<div>m: length of word<\/div>\n<div><\/div>\n<div><strong>Space Complexity:<\/strong><\/div>\n<div>O(n*m)<\/div>\n<div><\/div>\n<div><strong>Solution:<\/strong><\/div>\n<div>\n<pre class=\"lang:default decode:true  \">\/\/ Author: Huahua\r\nclass MagicDictionary {\r\npublic:\r\n    \/** Initialize your data structure here. *\/\r\n    MagicDictionary() {\r\n        dict_.clear();\r\n    }\r\n    \r\n    \/** Build a dictionary through a list of words *\/\r\n    void buildDict(vector&lt;string&gt; dict) {\r\n        for(string&amp; word: dict) {\r\n            for(int i = 0; i &lt; word.length(); ++i) {\r\n                char c = word[i];\r\n                word[i] = '*';\r\n                dict_[word].insert(c);\r\n                word[i] = c;\r\n            }\r\n        }\r\n    }\r\n    \r\n    \/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character *\/\r\n    bool search(string word) {\r\n        for(int i = 0; i &lt; word.length(); ++i) {\r\n            char c = word[i];\r\n            word[i] = '*';\r\n            if (dict_.count(word)) {\r\n                const auto&amp; char_set = dict_[word];\r\n                if (!char_set.count(c) || char_set.size() &gt; 1)\r\n                    return true;\r\n            }\r\n            word[i] = c;\r\n        }\r\n        return false;\r\n    }\r\nprivate:\r\n    unordered_map&lt;string, unordered_set&lt;char&gt;&gt; dict_;\r\n};\r\n\r\n\/**\r\n * Your MagicDictionary object will be instantiated and called as such:\r\n * MagicDictionary obj = new MagicDictionary();\r\n * obj.buildDict(dict);\r\n * bool param_2 = obj.search(word);\r\n *\/<\/pre>\n<\/div>\n<p>Java \/ Trie<\/p>\n<pre class=\"lang:c++ decode:true \">class MagicDictionary {\r\n    private Trie root;    \r\n    \r\n    public MagicDictionary() {\r\n        root = new Trie();\r\n    } \r\n    \r\n    public void buildDict(String[] dict) {\r\n        for (String word : dict) {\r\n            Trie curr = root;\r\n            for (char c : word.toCharArray()) {                \r\n                int index = c - 'a';\r\n                if (curr.children[index] == null)\r\n                    curr.children[index] = new Trie();\r\n                curr = curr.children[index];\r\n            }\r\n            curr.ends = true;\r\n        }\r\n    }  \r\n    \r\n    public boolean search(String word) {\r\n        char[] s = word.toCharArray();\r\n        for(int i = 0; i &lt; s.length; i++) {\r\n            for (char c = 'a'; c &lt;= 'z'; ++c) {\r\n                if (s[i] == c) continue;\r\n                char tmp = s[i];\r\n                s[i] = c;\r\n                if (contains(s)) return true;\r\n                s[i] = tmp;\r\n            }\r\n        }\r\n        return false;\r\n    }\r\n    \r\n    private boolean contains(char[] word) {        \r\n        Trie curr = root;\r\n        for (int i = 0; i &lt; word.length; ++i) {\r\n            curr = curr.children[word[i] - 'a'];\r\n            if (curr == null) return false;            \r\n        }\r\n        return curr.ends;\r\n    }\r\n    \r\n    class Trie {\r\n        private boolean ends;\r\n        private Trie[] children;\r\n        public Trie() {\r\n            children = new Trie[26];\r\n            ends = false;\r\n        }\r\n    }\r\n}<\/pre>\n<p>Java \/ Trie v2<\/p>\n<pre class=\"lang:java decode:true \">class MagicDictionary {\r\n    private Trie root;    \r\n    \r\n    public MagicDictionary() {\r\n        root = new Trie();\r\n    } \r\n    \r\n    public void buildDict(String[] dict) {\r\n        for (String word : dict) {\r\n            Trie curr = root;\r\n            for (char c : word.toCharArray()) {                \r\n                int index = c - 'a';\r\n                if (curr.children[index] == null)\r\n                    curr.children[index] = new Trie();\r\n                curr = curr.children[index];\r\n            }\r\n            curr.ends = true;\r\n        }\r\n    }  \r\n    \r\n    public boolean search(String word) {\r\n        char[] s = word.toCharArray();\r\n        Trie prefix = root;\r\n        for(int i = 0; i &lt; s.length; i++) {\r\n            for (char c = 'a'; c &lt;= 'z'; ++c) {\r\n                if (s[i] == c) continue;\r\n                char tmp = s[i];\r\n                s[i] = c;\r\n                if (contains(s, prefix, i)) return true;\r\n                s[i] = tmp;                \r\n            }\r\n            prefix = prefix.children[s[i] - 'a'];\r\n            if (prefix == null) return false;\r\n        }\r\n        return false;\r\n    }\r\n    \r\n    private boolean contains(char[] word, Trie prefix, int s) {        \r\n        Trie curr = prefix;\r\n        for (int i = s; i &lt; word.length; ++i) {\r\n            curr = curr.children[word[i] - 'a'];\r\n            if (curr == null) return false;\r\n        }\r\n        return curr.ends;\r\n    }\r\n    \r\n    class Trie {\r\n        private boolean ends;\r\n        private Trie[] children;\r\n        public Trie() {\r\n            children = new Trie[26];\r\n            ends = false;\r\n        }\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Implement a magic directory with\u00a0buildDict, and\u00a0search\u00a0methods. For the method\u00a0buildDict, you&#8217;ll be given a list of non-repetitive words to build a dictionary. For the method\u00a0search,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[144,143,145,96],"class_list":["post-227","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-contains","tag-dict","tag-transform","tag-trie","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/227","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=227"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/227\/revisions"}],"predecessor-version":[{"id":3077,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/227\/revisions\/3077"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}