{"id":1184,"date":"2017-12-11T15:33:34","date_gmt":"2017-12-11T23:33:34","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1184"},"modified":"2017-12-11T23:34:19","modified_gmt":"2017-12-12T07:34:19","slug":"leetcode-745-prefix-and-suffix-search","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-745-prefix-and-suffix-search\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 745. Prefix and Suffix Search"},"content":{"rendered":"<p>Link:\u00a0<a href=\"https:\/\/leetcode.com\/problems\/prefix-and-suffix-search\/description\/\">https:\/\/leetcode.com\/problems\/prefix-and-suffix-search\/description\/<\/a><\/p>\n<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 745. Prefix and Suffix Search - \u5237\u9898\u627e\u5de5\u4f5c EP129\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/a-4WbFqalIA?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>Given many\u00a0<code>words<\/code>,\u00a0<code>words[i]<\/code>\u00a0has weight\u00a0<code>i<\/code>.<\/p>\n<p>Design a class\u00a0<code>WordFilter<\/code>\u00a0that supports one function,\u00a0<code>WordFilter.f(String prefix, String suffix)<\/code>. It will return the word with given\u00a0<code>prefix<\/code>\u00a0and\u00a0<code>suffix<\/code>\u00a0with maximum weight. If no word exists, return -1.<\/p>\n<p><b>Examples:<\/b><\/p>\n<pre class=\"\">Input:\r\nWordFilter([\"apple\"])\r\nWordFilter.f(\"a\", \"e\") \/\/ returns 0\r\nWordFilter.f(\"b\", \"\") \/\/ returns -1\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li><code>words<\/code>\u00a0has length in range\u00a0<code>[1, 15000]<\/code>.<\/li>\n<li>For each test case, up to\u00a0<code>words.length<\/code>\u00a0queries\u00a0<code>WordFilter.f<\/code>\u00a0may be made.<\/li>\n<li><code>words[i]<\/code>\u00a0has length in range\u00a0<code>[1, 10]<\/code>.<\/li>\n<li><code>prefix, suffix<\/code>\u00a0have lengths in range\u00a0<code>[0, 10]<\/code>.<\/li>\n<li><code>words[i]<\/code>\u00a0and\u00a0<code>prefix, suffix<\/code>\u00a0queries consist of lowercase letters only.<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>Construct all possible filters<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Solution1:<\/strong><\/p>\n<p>C++<\/p>\n<p>Time complexity: O(NL^3 + QL)\u00a0 where N is the number of words, L is the max length of the word, Q is the number of queries.<\/p>\n<p>Space complexity: O(NL^3)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 482 ms\r\nclass WordFilter {\r\npublic:\r\n    WordFilter(const vector&lt;string&gt;&amp; words) {\r\n        int index = 0;\r\n        for (const string&amp; word : words) {\r\n            int n = word.length();\r\n            string prefix;\r\n            for (int i = 0; i &lt;= n; ++i) {\r\n                if (i &gt; 0) prefix += word[i - 1];\r\n                string suffix;\r\n                for (int j = n; j &gt;= 0; --j) {                    \r\n                    if (j != n) suffix = word[j] + suffix;\r\n                    const string key = prefix + \"_\" + suffix;\r\n                    filters_[key] = index;                    \r\n                }                \r\n            }\r\n            ++index;\r\n        }\r\n    }\r\n    \r\n    int f(string prefix, string suffix) {\r\n        const string key = prefix + \"_\" + suffix;\r\n        auto it = filters_.find(key);\r\n        if (it != filters_.end()) return it-&gt;second;\r\n        return -1;\r\n    }\r\nprivate:\r\n    unordered_map&lt;string, int&gt; filters_;\r\n};<\/pre>\n<p>Version #2<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 499 ms\r\nclass WordFilter {\r\npublic:\r\n    WordFilter(const vector&lt;string&gt;&amp; words) {\r\n        int index = 0;\r\n        for (const string&amp; word : words) {\r\n            int n = word.length();\r\n            vector&lt;string&gt; prefixes(n + 1, \"\");\r\n            vector&lt;string&gt; suffixes(n + 1, \"\");\r\n            for (int i = 0; i &lt; n; ++i) {\r\n                prefixes[i + 1] = prefixes[i] + word[i];\r\n                suffixes[i + 1] = word[n - i - 1] + suffixes[i];\r\n            }\r\n            \r\n            for (const string&amp; prefix : prefixes)          \r\n                for (const string&amp; suffix : suffixes)                              \r\n                    filters_[prefix + \"_\" + suffix] = index;            \r\n            ++index;\r\n        }        \r\n    }\r\n    \r\n    int f(string prefix, string suffix) {\r\n        const string key = prefix + \"_\" + suffix;\r\n        auto it = filters_.find(key);\r\n        if (it != filters_.end()) return it-&gt;second;\r\n        return -1;\r\n    }\r\nprivate:\r\n    unordered_map&lt;string, int&gt; filters_;\r\n};<\/pre>\n<p><strong>Solution 2<\/strong>:<\/p>\n<p>C++ \/ Trie<\/p>\n<p>Time complexity: O(NL^2 + QL)\u00a0 where N is the number of words, L is the max length of the word, Q is the number of queries.<\/p>\n<p>Space complexity: O(NL^2)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 572 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, int index) {\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            \/\/ Update index\r\n            p-&gt;index = index;\r\n        }\r\n        p-&gt;is_word = true;\r\n    }\r\n    \r\n    \r\n    \/** Returns the index of word that has the prefix. *\/\r\n    int startsWith(const string&amp; prefix) const {\r\n        auto node = find(prefix);\r\n        if (!node) return -1;\r\n        return node-&gt;index;\r\n    }\r\nprivate:\r\n    struct TrieNode {\r\n        TrieNode():index(-1), is_word(false), children(27, nullptr){}\r\n        \r\n        ~TrieNode() {\r\n            for (TrieNode* child : children)\r\n                if (child) delete child;\r\n        }\r\n        \r\n        int index;\r\n        int 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};\r\n\r\nclass WordFilter {\r\npublic:\r\n    WordFilter(vector&lt;string&gt; words) {        \r\n        for (int i = 0; i &lt; words.size(); ++i) {\r\n            const string&amp; w = words[i];            \r\n            string key = \"{\" + w;\r\n            trie_.insert(key, i);            \r\n            for (int j = 0; j &lt; w.size(); ++j) {\r\n                key = w[w.size() - j - 1] + key;                \r\n                trie_.insert(key, i);\r\n            }\r\n        }\r\n    }\r\n    \r\n    int f(string prefix, string suffix) {        \r\n        return trie_.startsWith(suffix + \"{\" + prefix);\r\n    }\r\nprivate:\r\n    Trie trie_;\r\n};<\/pre>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-676-implement-magic-dictionary\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 676. Implement Magic Dictionary<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-208-implement-trie-prefix-tree\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 208. Implement Trie (Prefix Tree)<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Link:\u00a0https:\/\/leetcode.com\/problems\/prefix-and-suffix-search\/description\/ Problem: Given many\u00a0words,\u00a0words[i]\u00a0has weight\u00a0i. Design a class\u00a0WordFilter\u00a0that supports one function,\u00a0WordFilter.f(String prefix, String suffix). It will return the word with given\u00a0prefix\u00a0and\u00a0suffix\u00a0with maximum weight. If no&#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,47,45],"tags":[97,186,96],"class_list":["post-1184","post","type-post","status-publish","format-standard","hentry","category-hashtable","category-string","category-tree","tag-prefix","tag-suffix","tag-trie","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1184","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=1184"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1184\/revisions"}],"predecessor-version":[{"id":1192,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1184\/revisions\/1192"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}