676 Implement Magic Dictionary

Search…
676. Implement Magic Dictionary​
1. Question
Implement a magic directory withbuildDict, andsearchmethods.
For the methodbuildDict, you'll be given a list of non-repetitive words to build a dictionary.
For the methodsearch, 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
Input: buildDict(["hello", "leetcode"]), Output: Null
2
Input: search("hello"), Output: False
3
Input: search("hhllo"), Output: True
4
Input: search("hell"), Output: False
5
Input: search("leetcoded"), Output: False
Copied!
Note:
1.You may assume that all the inputs are consist of lowercase lettersa-z.
2.For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
3.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.
2. Implementation
(1) HashMap
1
class MagicDictionary {
2
    Map <String, List<int[]>> map;
3
    /** Initialize your data structure here. */
4
    public MagicDictionary() {
5
        map = new HashMap<>();
6
    }
7
​
8
    /** Build a dictionary through a list of words */
9
    public void buildDict(String[] dict) {
10
        for (String word : dict) {
11
            for (int i = 0; i < word.length(); i++) {
12
                String key = word.substring(0, i) + word.substring(i + 1);
13
​
14
                int[] info = new int[] {i, word.charAt(i)};
15
​
16
                List<int[]> list = map.getOrDefault(key, new ArrayList<int[]>());
17
                list.add(info);
18
​
19
                map.put(key, list);
20
            }
21
        }
22
    }
23
​
24
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
25
    public boolean search(String word) {
26
        for (int i = 0; i < word.length(); i++) {
27
            String key = word.substring(0, i) + word.substring(i + 1);
28
​
29
            if (map.containsKey(key)) {
30
                for (int[] info : map.get(key)) {
31
                    if (i == info[0] && word.charAt(i) != info[1]) {
32
                        return true;
33
                    }
34
                }
35
            }
36
        }
37
        return false;
38
    }
39
}
40
​
41
/**
42
 * Your MagicDictionary object will be instantiated and called as such:
43
 * MagicDictionary obj = new MagicDictionary();
44
 * obj.buildDict(dict);
45
 * boolean param_2 = obj.search(word);
46
 */
Copied!
(2) Trie
1
class MagicDictionary {
2
    class TrieNode {
3
        char val;
4
        boolean isWord;
5
        TrieNode[] childNode;
6
​
7
        public TrieNode(char val) {
8
            this.val = val;
9
            childNode = new TrieNode[26];
10
        }
11
    }
12
​
13
    class Trie {
14
        TrieNode root;
15
​
16
        public Trie() {
17
            root = new TrieNode(' ');
18
        }
19
​
20
        public void insert(String word) {
21
            if (word == null || word.length() == 0) {
22
                return;
23
            }
24
​
25
            TrieNode curNode = root;
26
​
27
            for (char c : word.toCharArray()) {
28
                int index = c - 'a';
29
                if (curNode.childNode[index] == null) {
30
                    curNode.childNode[index] = new TrieNode(c);
31
                }
32
                curNode = curNode.childNode[index];
33
            }
34
            curNode.isWord = true;
35
        }
36
​
37
        public boolean search(String word) {
38
            if (word == null || word.length() == 0) {
39
                return false;
40
            }
41
​
42
            TrieNode curNode = root;
43
​
44
            for (char c : word.toCharArray()) {
45
                int index = c - 'a';
46
                if (curNode.childNode[index] == null) {
47
                    return false;
48
                }
49
                curNode = curNode.childNode[index];
50
            }
51
            return curNode.isWord;
52
        }
53
    }
54
​
55
    Trie trie;
56
​
57
    /** Initialize your data structure here. */
58
    public MagicDictionary() {
59
        trie = new Trie();
60
    }
61
​
62
    /** Build a dictionary through a list of words */
63
    public void buildDict(String[] dict) {
64
        for (String word : dict) {
65
            trie.insert(word);
66
        }
67
    }
68
​
69
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
70
    public boolean search(String word) {
71
        char[] letters = word.toCharArray();
72
        for (int i = 0; i < word.length(); i++) {
73
            char oldC = letters[i];
74
​
75
            for (char c = 'a'; c <= 'z'; c++) {
76
                if (c == oldC) {
77
                    continue;
78
                }
79
​
80
                letters[i] = c;
81
                String newWord = new String(letters);
82
                if (trie.search(newWord)) {
83
                    return true;
84
                }
85
            }
86
            letters[i] = oldC;
87
        }
88
        return false;
89
    }
90
}
91
​
92
/**
93
 * Your MagicDictionary object will be instantiated and called as such:
94
 * MagicDictionary obj = new MagicDictionary();
95
 * obj.buildDict(dict);
96
 * boolean param_2 = obj.search(word);
97
 */
Copied!
3. Time & Space Complexity
HashMap: 时间复杂度O(nm), n为dict里word的数量, m是dict里word的平均长度, 空间复杂度O(nm)
Trie: 时间复杂度build: O(nm), n为dict里word的数量, m是dict里word的平均长度, search: O(n * 25^m), 空间复杂度O(nm)
648 Replace Words
677 Map Sum Pairs
Last modified 2yr ago
Copy link
Contents
676. Implement Magic Dictionary
1. Question
2. Implementation
3. Time & Space Complexity
676. Implement Magic Dictionary​

1. Question

2. Implementation

3. Time & Space Complexity

676. Implement Magic Dictionary
