Link: https://leetcode.com/problems/prefix-and-suffix-search/description/
Problem:
Given many words, words[i] has weight i.
Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.
Examples:
|
1 2 3 4 |
Input: WordFilter(["apple"]) WordFilter.f("a", "e") // returns 0 WordFilter.f("b", "") // returns -1 |
Note:
wordshas length in range[1, 15000].- For each test case, up to
words.lengthqueriesWordFilter.fmay be made. words[i]has length in range[1, 10].prefix, suffixhave lengths in range[0, 10].words[i]andprefix, suffixqueries consist of lowercase letters only.
Idea:
Construct all possible filters
Solution1:
C++
Time complexity: O(NL^3 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.
Space complexity: O(NL^3)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua // Runtime: 482 ms class WordFilter { public: WordFilter(const vector<string>& words) { int index = 0; for (const string& word : words) { int n = word.length(); string prefix; for (int i = 0; i <= n; ++i) { if (i > 0) prefix += word[i - 1]; string suffix; for (int j = n; j >= 0; --j) { if (j != n) suffix = word[j] + suffix; const string key = prefix + "_" + suffix; filters_[key] = index; } } ++index; } } int f(string prefix, string suffix) { const string key = prefix + "_" + suffix; auto it = filters_.find(key); if (it != filters_.end()) return it->second; return -1; } private: unordered_map<string, int> filters_; }; |
Version #2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua // Runtime: 499 ms class WordFilter { public: WordFilter(const vector<string>& words) { int index = 0; for (const string& word : words) { int n = word.length(); vector<string> prefixes(n + 1, ""); vector<string> suffixes(n + 1, ""); for (int i = 0; i < n; ++i) { prefixes[i + 1] = prefixes[i] + word[i]; suffixes[i + 1] = word[n - i - 1] + suffixes[i]; } for (const string& prefix : prefixes) for (const string& suffix : suffixes) filters_[prefix + "_" + suffix] = index; ++index; } } int f(string prefix, string suffix) { const string key = prefix + "_" + suffix; auto it = filters_.find(key); if (it != filters_.end()) return it->second; return -1; } private: unordered_map<string, int> filters_; }; |
Solution 2:
C++ / Trie
Time complexity: O(NL^2 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.
Space complexity: O(NL^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// Author: Huahua // Runtime: 572 ms class Trie { public: /** Initialize your data structure here. */ Trie(): root_(new TrieNode()) {} /** Inserts a word into the trie. */ void insert(const string& word, int index) { TrieNode* p = root_.get(); for (const char c : word) { if (!p->children[c - 'a']) p->children[c - 'a'] = new TrieNode(); p = p->children[c - 'a']; // Update index p->index = index; } p->is_word = true; } /** Returns the index of word that has the prefix. */ int startsWith(const string& prefix) const { auto node = find(prefix); if (!node) return -1; return node->index; } private: struct TrieNode { TrieNode():index(-1), is_word(false), children(27, nullptr){} ~TrieNode() { for (TrieNode* child : children) if (child) delete child; } int index; int is_word; vector<TrieNode*> children; }; const TrieNode* find(const string& prefix) const { const TrieNode* p = root_.get(); for (const char c : prefix) { p = p->children[c - 'a']; if (p == nullptr) break; } return p; } std::unique_ptr<TrieNode> root_; }; class WordFilter { public: WordFilter(vector<string> words) { for (int i = 0; i < words.size(); ++i) { const string& w = words[i]; string key = "{" + w; trie_.insert(key, i); for (int j = 0; j < w.size(); ++j) { key = w[w.size() - j - 1] + key; trie_.insert(key, i); } } } int f(string prefix, string suffix) { return trie_.startsWith(suffix + "{" + prefix); } private: Trie trie_; }; |
Related Problems: