I like to read this solution as a small machine: keep the useful information, throw away the noise. For 843. Guess the Word, the solution in this repository is mainly a straightforward implementation 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: straightforward implementation.
The notes already sitting in the source point us in the right direction:
- Solution 2.1: Shuffle the Wordlist
- https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison
- time: O(N), space: O(N)
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 guess, match, findSecretWord, score.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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: O(N), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Solution 2.1: Shuffle the Wordlist
02//https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison
03//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Guess the Word.
04//Memory Usage: 6.2 MB, less than 98.02% of C++ online submissions for Guess the Word.
05//time: O(N), space: O(N)
06/**
07 * // This is the Master's API interface.
08 * // You should not implement it, or speculate about its implementation
09 * class Master {
10 * public:
11 * int guess(string word);
12 * };
13 */
14class Solution {
15public:
16 int match(string& a, string& b){
17 int matches = 0;
18
19 for(int i = 0; i < a.size(); ++i){
20 if(a[i] == b[i]) ++matches;
21 }
22
23 return matches;
24 };
25
26 void findSecretWord(vector<string>& wordlist, Master& master) {
27 random_shuffle(wordlist.begin(), wordlist.end());
28
29 for(int i = 0; i < 10 && !wordlist.empty(); ++i){
30 int diff = master.guess(wordlist[0]);
31 //only retain the words who has "diff" different char with the guessed word
32 vector<string> tmp;
33 copy_if(wordlist.begin(), wordlist.end(),
34 back_inserter(tmp),
35 [&diff, &wordlist, this](string& w){
36 return match(wordlist[0], w) == diff;}
37 );
38 swap(wordlist, tmp);
39 }
40 }
41};
42
43//Solution 2.2: Guess a Random Word
44//https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison
45//WA
46//5 / 6 test cases passed.
47//time: O(N), space: O(N)
48/**
49 * // This is the Master's API interface.
50 * // You should not implement it, or speculate about its implementation
51 * class Master {
52 * public:
53 * int guess(string word);
54 * };
55 */
56class Solution {
57public:
58 int match(string& a, string& b){
59 int matches = 0;
60
61 for(int i = 0; i < a.size(); ++i){
62 if(a[i] == b[i]) ++matches;
63 }
64
65 return matches;
66 };
67
68 void findSecretWord(vector<string>& wordlist, Master& master) {
69 random_shuffle(wordlist.begin(), wordlist.end());
70
71 for(int i = 0; i < 10 && !wordlist.empty(); ++i){
72 string guessword = wordlist[rand()%wordlist.size()];
73 int diff = master.guess(guessword);
74 //only retain the words who has "diff" different char with the guessed word
75 vector<string> tmp;
76 copy_if(wordlist.begin(), wordlist.end(),
77 back_inserter(tmp),
78 [&diff, &guessword, this](string& w){
79 return match(guessword, w) == diff;}
80 );
81 swap(wordlist, tmp);
82 }
83 }
84};
85
86//Solution 3: Minimax(minimize a certain maxima heuristic rather the the Minimax algorithm in AI)
87//https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison
88//Runtime: 12 ms, faster than 27.33% of C++ online submissions for Guess the Word.
89//Memory Usage: 6.7 MB, less than 29.88% of C++ online submissions for Guess the Word.
90//time: O(N^2), space: O(N)
91/**
92 * // This is the Master's API interface.
93 * // You should not implement it, or speculate about its implementation
94 * class Master {
95 * public:
96 * int guess(string word);
97 * };
98 */
99class Solution {
100public:
101 int match(string& a, string& b){
102 int matches = 0;
103
104 for(int i = 0; i < a.size(); ++i){
105 if(a[i] == b[i]) ++matches;
106 }
107
108 return matches;
109 };
110
111 void findSecretWord(vector<string>& wordlist, Master& master) {
112 for(int i = 0; i < 10 && !wordlist.empty(); ++i){
113 //(word, count of words who has 0 match with the key)
114 unordered_map<string, int> counter;
115
116 for(string& a : wordlist){
117 for(string& b : wordlist){
118 if(match(a, b) == 0) ++counter[a];
119 }
120 }
121
122 // cout << "counter built: " << counter.size() << endl;
123
124 //guess the word having minimum 0-matching words
125 string guessword = *min_element(wordlist.begin(), wordlist.end(),
126 [&counter](const string& a, const string& b){
127 return counter[a] < counter[b];
128 });
129
130 //about 80% of prob the diff will be 0
131 int diff = master.guess(guessword);
132
133 // cout << "guess: " << guessword << ", " << diff << endl;
134
135 /*
136 since guessword has least 0-matching words,
137 so we can retain least words in next iteration
138 */
139 vector<string> tmp;
140 copy_if(wordlist.begin(), wordlist.end(),
141 back_inserter(tmp),
142 [&diff, &guessword, this](string& w){
143 return match(guessword, w) == diff;}
144 );
145 swap(wordlist, tmp);
146
147 // cout << "wordlist: " << wordlist.size() << endl;
148 }
149 }
150};
151
152//Solution 4: Count the Occurrence of Characters
153//https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison
154//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Guess the Word.
155//Memory Usage: 6.6 MB, less than 48.26% of C++ online submissions for Guess the Word.
156//time: O(N), space: O(N)
157class Solution {
158public:
159 //(pos, char) -> count
160 vector<vector<int>> counter;
161
162 int match(string& a, string& b){
163 int matches = 0;
164
165 for(int i = 0; i < a.size(); ++i){
166 if(a[i] == b[i]) ++matches;
167 }
168
169 return matches;
170 };
171
172 int score(string& w){
173 int res = 0;
174
175 for(int i = 0; i < 6; ++i){
176 res += counter[i][w[i]-'a'];
177 }
178
179 return res;
180 };
181
182 void findSecretWord(vector<string>& wordlist, Master& master) {
183 for(int i = 0; i < 10 && !wordlist.empty(); ++i){
184 counter = vector<vector<int>>(6, vector<int>(26, 0));
185
186 for(string& word : wordlist){
187 for(int j = 0; j < 6; ++j){
188 ++counter[j][word[j]-'a'];
189 }
190 }
191
192 //guess the word who has most same char on same position
193 string guessword = *max_element(wordlist.begin(), wordlist.end(),
194 [this](string& a, string& b){
195 return score(a) < score(b);
196 });
197
198 int diff = master.guess(guessword);
199
200 // cout << "guess: " << guessword << ", " << diff << endl;
201
202 vector<string> tmp;
203 copy_if(wordlist.begin(), wordlist.end(),
204 back_inserter(tmp),
205 [&diff, &guessword, this](string& w){
206 return match(guessword, w) == diff;}
207 );
208 swap(wordlist, tmp);
209
210 // cout << "wordlist: " << wordlist.size() << endl;
211 }
212 }
213};Cost
Complexity
Time
O(N), space: O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.