Problem:
Implement a magic directory with buildDict
, and search
methods.
For the method buildDict
, you’ll be given a list of non-repetitive words to build a dictionary.
For the method search
, you’ll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.
Example 1:
1 2 3 4 5 |
Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False |
Note:
- You may assume that all the inputs are consist of lowercase letters
a-z
. - For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
- Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.
Idea:
Fuzzy match
Time Complexity:
buildDict: O(n*m)
n: numbers of words
m: length of word
search: O(m)
m: length of word
Space Complexity:
O(n*m)
Solution:
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 |
// Author: Huahua class MagicDictionary { public: /** Initialize your data structure here. */ MagicDictionary() { dict_.clear(); } /** Build a dictionary through a list of words */ void buildDict(vector<string> dict) { for(string& word: dict) { for(int i = 0; i < word.length(); ++i) { char c = word[i]; word[i] = '*'; dict_[word].insert(c); word[i] = c; } } } /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */ bool search(string word) { for(int i = 0; i < word.length(); ++i) { char c = word[i]; word[i] = '*'; if (dict_.count(word)) { const auto& char_set = dict_[word]; if (!char_set.count(c) || char_set.size() > 1) return true; } word[i] = c; } return false; } private: unordered_map<string, unordered_set<char>> dict_; }; /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dict); * bool param_2 = obj.search(word); */ |
Java / Trie
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 |
class MagicDictionary { private Trie root; public MagicDictionary() { root = new Trie(); } public void buildDict(String[] dict) { for (String word : dict) { Trie curr = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (curr.children[index] == null) curr.children[index] = new Trie(); curr = curr.children[index]; } curr.ends = true; } } public boolean search(String word) { char[] s = word.toCharArray(); for(int i = 0; i < s.length; i++) { for (char c = 'a'; c <= 'z'; ++c) { if (s[i] == c) continue; char tmp = s[i]; s[i] = c; if (contains(s)) return true; s[i] = tmp; } } return false; } private boolean contains(char[] word) { Trie curr = root; for (int i = 0; i < word.length; ++i) { curr = curr.children[word[i] - 'a']; if (curr == null) return false; } return curr.ends; } class Trie { private boolean ends; private Trie[] children; public Trie() { children = new Trie[26]; ends = false; } } } |
Java / Trie v2
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 |
class MagicDictionary { private Trie root; public MagicDictionary() { root = new Trie(); } public void buildDict(String[] dict) { for (String word : dict) { Trie curr = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (curr.children[index] == null) curr.children[index] = new Trie(); curr = curr.children[index]; } curr.ends = true; } } public boolean search(String word) { char[] s = word.toCharArray(); Trie prefix = root; for(int i = 0; i < s.length; i++) { for (char c = 'a'; c <= 'z'; ++c) { if (s[i] == c) continue; char tmp = s[i]; s[i] = c; if (contains(s, prefix, i)) return true; s[i] = tmp; } prefix = prefix.children[s[i] - 'a']; if (prefix == null) return false; } return false; } private boolean contains(char[] word, Trie prefix, int s) { Trie curr = prefix; for (int i = s; i < word.length; ++i) { curr = curr.children[word[i] - 'a']; if (curr == null) return false; } return curr.ends; } class Trie { private boolean ends; private Trie[] children; public Trie() { children = new Trie[26]; ends = false; } } } |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment