https://leetcode.com/problems/implement-magic-dictionary/description/
X.
X. Using Trie
X. Trie
https://leetcode.com/problems/implement-magic-dictionary/discuss/177342/66ms-Prefix-Tree-(Trie)-Java-with-Explanation
https://leetcode.com/problems/implement-magic-dictionary/discuss/107465/Efficient-Trie-and-Java-8-w-Explanation
First build a trie tree, and in search(String word) function, we just edit every character from 'a' to 'z' and search the new string.
(This process is like "word ladder")
Approach #1: Brute Force with Bucket-By-Length [Accepted]
https://zxi.mytechroad.com/blog/hashtable/leetcode-676-implement-magic-dictionary/
https://leetcode.com/problems/implement-magic-dictionary/discuss/107446/Easy-14-lines-Java-solution-HashMap
X. http://www.cnblogs.com/grandyang/p/7612918.html
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:
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.
X.
// len->
private Map<Integer, TreeSet<String>> map = new HashMap<>();
/** Initialize your data structure here. */
public MagicDictionary() {
}
/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
for (String word : dict) {
map.computeIfAbsent(word.length(), li -> new TreeSet<>()).add(word);
}
}
/**
* Returns if there is any word in the trie that equals to the given word after
* modifying exactly one character
*/
public boolean search(String word) {
if (!map.containsKey(word.length())) {
return false;
}
TreeSet<String> set = map.get(word.length());
// <
String floor = set.lower(word);
char[] charArray = word.toCharArray();
if (floor != null && isDistanceOne(charArray, floor.toCharArray())) {
return true;
}
// >
String ceil = set.higher(word);
if (ceil != null && isDistanceOne(charArray, ceil.toCharArray())) {
return true;
}
return false;
}
// hello, hello should return false;
private boolean isDistanceOne(char[] word1, char[] word2) {
if (word1.length != word2.length)
return false;
int diff = 0;
for (int i = 0; i < word1.length; i++) {
if (word1[i] != word2[i]) {
diff++;
if (diff >= 2)
return false;
}
}
// BUG: not return true;
return diff == 1;
}
X. Using Trie
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;
}
}
}
|
https://leetcode.com/problems/implement-magic-dictionary/discuss/177342/66ms-Prefix-Tree-(Trie)-Java-with-Explanation
We could build a trie using word in dicts. If two words differ by one character only, they will be within the branches regardless of the mismatched character.
For example, dict = ["ooo", "ooa"] and search("oxo"), they have one character mismatched,
o - o [mismatched here, cntMismatched = 1] - a [mismatched here, cntMismatched = 2, backtrack]
- o - exhausted [cntMismatched = 1, return true] private static Node root;
public MagicDictionary() {
root = new Node();
}
/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
buildTrie(dict);
}
private void buildTrie(String[] dict) {
Node ptr;
for (String word : dict) {
ptr = root;
for (char ch : word.toCharArray()) {
int order = ch - 'a';
if (ptr.children[order] == null)
ptr.children[order] = new Node();
ptr = ptr.children[order];
}
ptr.isWordEnd = true;
}
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
public boolean search(String word) {
return dfs(0, word, root, 0);
}
private boolean dfs(int curId, String word, Node parentPtr, int cntMismatched) {
if (cntMismatched > 1) {
return false;
}
if (curId == word.length()) {
return parentPtr.isWordEnd && cntMismatched == 1;
}
for (int i = 0; i < 26; i++) {
int order = word.charAt(curId) - 'a';
if (parentPtr.children[i] == null)
continue;
if (order != i) {
if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched + 1))
return true;
} else {
if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched))
return true;
}
}
return false;
}
class Node {
Node[] children;
boolean isWordEnd;
public Node() {
children = new Node[26];
isWordEnd = false;
}
}
This solution beats 93.56% java solutions.
Trie trie;
public MagicDictionary() {
trie = new Trie(256);
}
public void buildDict(String[] dict) {
Arrays.stream(dict).forEach(s -> trie.insert(s));
}
public boolean search(String word) {
return trie.relaxedSearch(word);
}
class Trie {
private int R;
private TrieNode root;
public Trie(int R) {
this.R = R;
root = new TrieNode();
}
public boolean relaxedSearch(String word) {
return relaxedSearch(root, word, 0);
}
private boolean relaxedSearch(TrieNode root, String word, int changedTimes) {
if (root == null || (!root.isWord && word.isEmpty()) || changedTimes > 1) return false;
if (root.isWord && word.isEmpty()) return changedTimes == 1;
return Arrays.stream(root.next).anyMatch(nextNode -> relaxedSearch(nextNode, word.substring(1),
root.next[word.charAt(0)] == nextNode ? changedTimes : changedTimes+1));
}
// Inserts a word into the trie.
public void insert(String word) {
insert(root, word);
}
private void insert(TrieNode root, String word) {
if (word.isEmpty()) { root.isWord = true; return; }
if (root.next[word.charAt(0)] == null) root.next[word.charAt(0)] = new TrieNode();
insert(root.next[word.charAt(0)], word.substring(1));
}
private class TrieNode {
private TrieNode[] next = new TrieNode[R];
private boolean isWord;
}
}First build a trie tree, and in search(String word) function, we just edit every character from 'a' to 'z' and search the new string.
(This process is like "word ladder")
if k is the average length of input string, you are using O(nk) for building the Trie and O(26k^2) for searching the Trie.. That's a really bad application for Trie.
If you really want to iterate all 26 alphabet possibilities (which is unnecessary), why don't you just use a HashSet. so O(n) for building the set and O(26k) for searching?
By changing every character and then search in Trie, the advantage of the Trie is completely lost, maybe even worst than use a set. @bianhit 's implementation takes the advantage of Trie.
if k is the average length of input string, you are using O(nk) for building the Trie and O(26k^2) for searching the Trie.. That's a really bad application for Trie.
If you really want to iterate all 26 alphabet possibilities (which is unnecessary), why don't you just use a HashSet. so O(n) for building the set and O(26k) for searching?
By changing every character and then search in Trie, the advantage of the Trie is completely lost, maybe even worst than use a set. @bianhit 's implementation takes the advantage of Trie.
if k is the average length of input string, you are using O(nk) for building the Trie and O(26k^2) for searching the Trie.. That's a really bad application for Trie.
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord;
public TrieNode() {}
}
TrieNode root;
/** Initialize your data structure here. */
public MagicDictionary() {
root = new TrieNode();
}
/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
for (String s : dict) {
TrieNode node = root;
for (char c : s.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isWord = true;
}
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
public boolean search(String word) {
char[] arr = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (arr[i] == c) {
continue;
}
char org = arr[i];
arr[i] = c;
if (helper(new String(arr), root)) {
return true;
}
arr[i] = org;
}
}
return false;
}
public boolean helper(String s, TrieNode root) {
TrieNode node = root;
for (char c : s.toCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return node.isWord;
}
Let's say a word 'apple' has generalized neighbors '*pple', 'a*ple', 'ap*le', 'app*e', and 'appl*'. When searching for whether a word like 'apply' has a neighbor like 'apple', we only need to know whether they have a common generalized neighbor.
Continuing the above thinking, one issue is that 'apply' is not a neighbor with itself, yet it has the same generalized neighbor '*pply'. To remedy this, we'll count how many sources generated '*pply'. If there are 2 or more, then one of them won't be 'apply'. If there is exactly one, we should check that it wasn't 'apply'. In either case, we can be sure that there was some magic word generating '*pply' that wasn't 'apply'.
- Time Complexity: to build and to search, where is the length of
words[i], and is the length of our search word. - Space Complexity: , the space used by
count. We also use space when generating neighbors to search.
Set<String> words; Map<String, Integer> count; public MagicDictionary() { words = new HashSet(); count = new HashMap(); } private ArrayList<String> generalizedNeighbors(String word) { ArrayList<String> ans = new ArrayList(); char[] ca = word.toCharArray(); for (int i = 0; i < word.length(); ++i) { char letter = ca[i]; ca[i] = '*'; String magic = new String(ca); ans.add(magic); ca[i] = letter; } return ans; } public void buildDict(String[] words) { for (String word: words) { this.words.add(word); for (String nei: generalizedNeighbors(word)) { count.put(nei, count.getOrDefault(nei, 0) + 1); } } } public boolean search(String word) { for (String nei: generalizedNeighbors(word)) { int c = count.getOrDefault(nei, 0); if (c > 1 || c == 1 && !words.contains(word)) return true; } return false; }
只不过这道题的两个单词之间长度必须相等。所以只需检测和要搜索单词长度一样的单词即可，所以我们用的数据结构就是根据单词的长度来分，把长度相同相同的单词放到一起，这样就可以减少搜索量。那么对于和要搜索单词进行比较的单词，由于已经保证了长度相等，我们直接进行逐个字符比较即可，用cnt表示不同字符的个数，初始化为0。如果当前遍历到的字符相等，则continue；如果当前遍历到的字符不相同，并且此时cnt已经为1了，则break，否则cnt就自增1。退出循环后，我们检测是否所有字符都比较完了且cnt为1，是的话则返回true，否则就是跟下一个词比较。如果所有词都比较完了，则返回false
https://leetcode.com/articles/implement-magic-dictionary/Approach #1: Brute Force with Bucket-By-Length [Accepted]
- Time Complexity: to build and to search, where is the number of
wordsin our magic dictionary, is the total number of letters in it, and is the length of the search word. - Space Complexity: , the space used by
buckets.
class MagicDictionary { Map<Integer, ArrayList<String>> buckets; public MagicDictionary() { buckets = new HashMap(); } public void buildDict(String[] words) { for (String word: words) { buckets.computeIfAbsent(word.length(), x -> new ArrayList()).add(word); } } public boolean search(String word) { if (!buckets.containsKey(word.length())) return false; for (String candidate: buckets.get(word.length())) { int mismatch = 0; for (int i = 0; i < word.length(); ++i) { if (word.charAt(i) != candidate.charAt(i)) { if (++mismatch > 1) break; } } if (mismatch == 1) return true; } return false; }
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_;
https://leetcode.com/problems/implement-magic-dictionary/discuss/107446/Easy-14-lines-Java-solution-HashMap
- For each word in
dict, for each char, remove the char and put the rest of the word as key, a pair of index of the removed char and the char aspart ofvalue list into a map. e.g.
"hello" -> {"ello":[[0, 'h']], "hllo":[[1, 'e']], "helo":[[2, 'l'],[3, 'l']], "hell":[[4, 'o']]} - During search, generate the keys as in step 1. When we see there's pair of same index but different char in the value array, we know the answer is true. e.g.
"healo" when removea, key is "helo" and there is a pair [2, 'l'] which has same index but different char. Then the answer is true;
class MagicDictionary {
Map<String, List<int[]>> map = new HashMap<>();
/** Initialize your data structure here. */
public MagicDictionary() {
}
/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
for (String s : dict) {
for (int i = 0; i < s.length(); i++) {
String key = s.substring(0, i) + s.substring(i + 1);
int[] pair = new int[] {i, s.charAt(i)};
List<int[]> val = map.getOrDefault(key, new ArrayList<int[]>());
val.add(pair);
map.put(key, val);
}
}
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
public boolean search(String word) {
for (int i = 0; i < word.length(); i++) {
String key = word.substring(0, i) + word.substring(i + 1);
if (map.containsKey(key)) {
for (int[] pair : map.get(key)) {
if (pair[0] == i && pair[1] != word.charAt(i)) return true;
}
}
}
return false;
}
X. http://www.cnblogs.com/grandyang/p/7612918.html
void buildDict(vector<string> dict) { for (string word : dict) s.insert(word); } /** 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.size(); ++i) { char t = word[i]; for (char c = 'a'; c <= 'z'; ++c) { if (c == t) continue; word[i] = c; if (s.count(word)) return true; } word[i] = t; } return false; } private: unordered_set<string> s;
