A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 676. Implement Magic Dictionary, the solution in this repository is mainly a trie solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: trie.
The notes already sitting in the source point us in the right direction:
- Approach #1: Brute Force with Bucket-By-Length [Accepted]
- S: total letter count, N: dict length, K: length of the word to be searched
- time: O(S) to build, O(NK) to search
- space: O(S)
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are buildDict, search, genneighbors.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: build: O(sigma(w_i^2)), search: O(K^2)
- Space: counter: O(sigma(w_i^2)), neighbors of word to be searched : O(K^2)
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Approach #1: Brute Force with Bucket-By-Length [Accepted]
02//Runtime: 4 ms, faster than 69.86% of C++ online submissions for Implement Magic Dictionary.
03//Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Implement Magic Dictionary.
04//S: total letter count, N: dict length, K: length of the word to be searched
05//time: O(S) to build, O(NK) to search
06//space: O(S)
07class MagicDictionary {
08public:
09 map<int, vector<string>> buckets;
10
11 /** Initialize your data structure here. */
12 MagicDictionary() {
13 }
14
15 /** Build a dictionary through a list of words */
16 void buildDict(vector<string> dict) {
17 for(string& word : dict){
18 buckets[word.size()].push_back(word);
19 }
20 }
21
22 /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
23 bool search(string word) {
24 bool flag = false;
25
26 for(string& candidate : buckets[word.size()]){
27 int dist = 0;
28 for(int i = 0; i < word.size(); i++){
29 if(word[i] != candidate[i]){
30 dist++;
31 }
32 if(dist > 1){
33 break;
34 }
35 }
36
37 if(dist == 1){
38 flag = true;
39 break;
40 }
41 }
42
43 return flag;
44 }
45};
46
47/**
48 * Your MagicDictionary object will be instantiated and called as such:
49 * MagicDictionary* obj = new MagicDictionary();
50 * obj->buildDict(dict);
51 * bool param_2 = obj->search(word);
52 */
53
54//Approach #2: Generalized Neighbors
55//Runtime: 4 ms, faster than 69.86% of C++ online submissions for Implement Magic Dictionary.
56//Memory Usage: 9.3 MB, less than 66.67% of C++ online submissions for Implement Magic Dictionary.
57//wi: length of words[i], K: length of the word to be searched
58//time: build: O(sigma(w_i^2)), search: O(K^2)
59//space: counter: O(sigma(w_i^2)), neighbors of word to be searched : O(K^2)
60class MagicDictionary {
61public:
62 set<string> dictset;
63 map<string, int> counter;
64
65 /** Initialize your data structure here. */
66 MagicDictionary() {
67
68 }
69
70 vector<string> genneighbors(string& word){
71 vector<string> neighbors;
72
73 for(int i = 0; i < word.size(); i++){
74 neighbors.push_back(word.substr(0, i) + "*" + word.substr(i+1));
75 }
76
77 return neighbors;
78 }
79
80 /** Build a dictionary through a list of words */
81 void buildDict(vector<string> dict) {
82 //counter : record possible neighbors' counts
83 for(string& word : dict){
84 vector<string> neighbors = genneighbors(word);
85 for(string& neighbor : neighbors){
86 counter[neighbor]++;
87 }
88 dictset.insert(word);
89 }
90 }
91
92 /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
93 bool search(string word) {
94 bool flag = false;
95 vector<string> neighbors = genneighbors(word);
96
97 for(string& neighbor : neighbors){
98 //if word has more than 1 neighbor, then one of them must not be word
99 //if word has only 1 neighbor, we need to check whether the neighbor is generated from word itself
100 if(counter[neighbor] > 1 || (counter[neighbor] == 1 && dictset.find(word) == dictset.end())){
101 flag = true;
102 break;
103 }
104 }
105
106 return flag;
107 }
108};
109
110/**
111 * Your MagicDictionary object will be instantiated and called as such:
112 * MagicDictionary* obj = new MagicDictionary();
113 * obj->buildDict(dict);
114 * bool param_2 = obj->search(word);
115 */
116
117//Trie
118//https://leetcode.com/problems/implement-magic-dictionary/discuss/107453/Easiest-JAVA-with-Trie-no-need-to-count-the-number-of-changes
119//Runtime: 76 ms, faster than 7.67% of C++ online submissions for Implement Magic Dictionary.
120//Memory Usage: 136.9 MB, less than 33.33% of C++ online submissions for Implement Magic Dictionary.
121class TrieNode {
122public:
123 vector<TrieNode*> children;
124 bool isEnd;
125
126 TrieNode(){
127 children = vector<TrieNode*>(26);
128 //initialize bool to avoid the following error!
129 //runtime error: load of value 190, which is not a valid value for type 'bool' (solution.cpp)
130 isEnd = false;
131 }
132};
133
134class MagicDictionary {
135public:
136 TrieNode* root;
137 /** Initialize your data structure here. */
138 MagicDictionary() {
139 root = new TrieNode();
140 }
141
142 /** Build a dictionary through a list of words */
143 void buildDict(vector<string> dict) {
144 for(string& word : dict){
145 for(int i = 0; i < word.size(); i++){
146 string neighbor = word;
147 //generate its 25 neighbors(by replacing 1 char)
148 for(int j = 0; j < 26; j++){
149 if('a'+j == word[i]) continue;
150 neighbor[i] = 'a'+j;
151 //put the neighbor into trie
152 TrieNode* cur = root;
153 for(char c : neighbor){
154 if(cur->children[c-'a'] == NULL){
155 cur->children[c-'a'] = new TrieNode();
156 }
157 cur = cur->children[c-'a'];
158 }
159 cur->isEnd = true;
160 }
161 }
162 }
163 }
164
165 /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
166 bool search(string word) {
167 TrieNode* cur = root;
168 for(char c : word){
169 cur = cur->children[c-'a'];
170 if(cur == NULL) return false;
171 }
172 return cur->isEnd;
173 }
174};
175
176/**
177 * Your MagicDictionary object will be instantiated and called as such:
178 * MagicDictionary* obj = new MagicDictionary();
179 * obj->buildDict(dict);
180 * bool param_2 = obj->search(word);
181 */Cost
Complexity
Time
build: O(sigma(w_i^2)), search: O(K^2)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
counter: O(sigma(w_i^2)), neighbors of word to be searched : O(K^2)
Auxiliary state plus the answer structure where the problem requires one.