Editorial: LeetCode 843 Guess the Word
https://leetcode.com/problems/guess-the-word/ from Google
Solutions:
The main idea is to use the return value of Master.guess(word) to eliminate other words. For example, if our secret is abcdef, and the word we guess is abcccc, then the return value will be 3. We know that if there’s another word only has 2 exact match comparing to abcccc, like abdddd, it’s impossible for this word to be the secret as it misses at least one character.
Likewise, if there’s another word which has 4 exact match comparing to abccdd, it’s not possible for this word to be the secret as it has one more match which is not in the secret. With this, we know that whenever we guess one word, we need to use this word to filter other words with the return value.
However, how do we pick the word in the first place?
1. Random pick (Can’t pass)
We shaffle the input wordlist first. Then we guess from the beginning of the wordlist. This can’t always pass.
1class Solution {
2public:
3 void findSecretWord(vector<string>& wordlist, Master& master) {
4 int N = wordlist.size();
5 vector<bool> suspect(N, true);
6 int guess_num = 10;
7 int guess_idx = 0;
8 int rest = N;
9 random_shuffle(wordlist.begin(), wordlist.end());
10 while (guess_num--) {
11 while (guess_idx < N and !suspect[guess_idx])
12 guess_idx++;
13 if (guess_idx == N)
14 break;
15 int ret = master.guess(wordlist[guess_idx]);
16 if (ret == 6)
17 break;
18 suspect[guess_idx] = false;
19 for (int i=guess_idx+1; i<N; i++) {
20 if (!suspect[i]) continue;
21 if (same(wordlist, guess_idx, i) != ret) {
22 suspect[i] = false;
23 rest--;
24 }
25 }
26 }
27 }
28private:
29 bool same(vector<string>& wordlist, int g, int i) {
30 int ans = 0;
31 for (int j=0; j<6; j++) {
32 if (wordlist[g][j] == wordlist[i][j])
33 ans++;
34 }
35 return ans;
36 }
37};
Time complexity: O(N). Space complexity: O(N).
2. Pick the highest score (beats 100%)
Calculate the score of each words based on their frequency. By frequency, we mean the frequence for the character to show up at a given index. For example, at index 0, we count how many times a shows up, how many times b shows up … and so on. Then, to calculate the score of a single word, we just sum up the frequency of that word.
The reason why we do this is because, if we pick a word which has no match against to other words, then we basically can’t eliminate many words if this word is not the answer. For example, if the word we guess is zzzzzz, and the return value is 0, we’ll eliminate nothing if all other words are like aaaaab, aaaaac, … and so on (because the exact match will be 0 for all other words).
As a result, picking this word first seems like a waste unless it’s the correct answer, but the probability is very low. Therefore, we sort the words based on the score, and then guess from the highest score one.
1class Solution {
2public:
3 vector<pair<int, int>> scores;
4 void buildScores(vector<string>& wordlist) {
5 int N = wordlist.size();
6 vector<vector<int>> cnt(6, vector<int>(26));
7 for (auto w : wordlist) for (int i=0; i<6; i++) cnt[i][w[i]-'a']++;
8 for (int j=0; j<N; j++) {
9 auto& w = wordlist[j];
10 int s = 0;
11 for (int i=0; i<6; i++) {
12 s += cnt[i][w[i]-'a'];
13 }
14 // negate the score so that the first element after sort is the highest score one
15 scores.push_back({-s, j});
16 }
17 sort(begin(scores), end(scores));
18 }
19 int same(vector<string>& wordlist, int g, int i) {
20 int ans = 0;
21 for (int j=0; j<6; j++) {
22 if (wordlist[g][j] == wordlist[i][j])
23 ans++;
24 }
25 return ans;
26 }
27 void findSecretWord(vector<string>& wordlist, Master& master) {
28 int N = wordlist.size();
29 buildScores(wordlist);
30 vector<bool> suspect(N, true);
31 int guess_num = 10;
32 int guess_idx = 0;
33 while (guess_num--) {
34 while (guess_idx < N and !suspect[guess_idx])
35 guess_idx++;
36 if (guess_idx == N)
37 break;
38 int wordIndex = scores[guess_idx].second;
39 int ret = master.guess(wordlist[wordIndex]);
40 if (ret == 6)
41 break;
42 suspect[guess_idx] = false;
43 for (int i=guess_idx; i<N; i++) {
44 if (!suspect[i]) continue;
45 if (same(wordlist, wordIndex, scores[i].second) != ret) {
46 suspect[i] = false;
47 }
48 }
49 }
50 }
51};
Time complexity: O(NlogN). Space complexity: O(N).