# [LeetCode] 843. Guess the Word 猜单词

2021年09月15日 阅读数：1

This problem is an interactive problem new to the LeetCode platform.html

We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as secret.java

You may call `master.guess(word)` to guess a word.  The guessed word should have type `string` and must be from the original list with 6 lowercase letters.python

This function returns an `integer` type, representing the number of exact matches (value and position) of your guess to the secret word.  Also, if your guess is not in the given wordlist, it will return `-1 `instead.app

For each test case, you have 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or less calls to `master.guess` and at least one of these guesses was the secret, you pass the testcase.less

Besides the example test case below, there will be 5 additional test cases, each with 100 words in the word list.  The letters of each word in those testcases were chosen independently at random from `'a'` to `'z'`, such that every word in the given word lists is unique.dom

```Example 1:
Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]

Explanation:

`master.guess("aaaaaa")` returns -1, because `"aaaaaa"` is not in wordlist.
`master.guess("acckzz") `returns 6, because `"acckzz"` is secret and has all 6 matches.
`master.guess("ccbazz")` returns 3, because` "ccbazz"` has 3 matches.
`master.guess("eiowzz")` returns 2, because `"eiowzz"` has 2 matches.
`master.guess("abcczz")` returns 4, because `"abcczz"` has 4 matches.

We made 5 calls to master.guess and one of them was the secret, so we pass the test case.
```

Note:  Any solutions that attempt to circumvent the judge will result in disqualification.ide

Java:

```public void findSecretWord(String[] wordlist, Master master) {
for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
HashMap<String, Integer> count = new HashMap<>();
for (String w1 : wordlist)
for (String w2 : wordlist)
if (match(w1, w2) == 0)
count.put(w1, count.getOrDefault(w1 , 0) + 1);
Pair<String, Integer> minimax = new Pair<>("", 1000);
for (String w : wordlist)
if (count.getOrDefault(w, 0) < minimax.getValue())
minimax = new Pair<>(w, count.getOrDefault(w, 0));
x = master.guess(minimax.getKey());
List<String> wordlist2 = new ArrayList<String>();
for (String w : wordlist)
if (match(minimax.getKey(), w) == x)
wordlist = wordlist2.toArray(new String);
}
}　　```

Python:

```# Time:  O(n^2)
# Space: O(n)

import collections
import itertools

class Solution(object):
def findSecretWord(self, wordlist, master):
"""
:type wordlist: List[Str]
:type master: Master
:rtype: None
"""
def solve(H, possible):
min_max_group, best_guess = possible, None
for guess in possible:
groups = [[] for _ in xrange(7)]
for j in possible:
if j != guess:
groups[H[guess][j]].append(j)
max_group = max(groups, key=len)
if len(max_group) < len(min_max_group):
min_max_group, best_guess = max_group, guess
return best_guess

H = [[sum(a == b for a, b in itertools.izip(wordlist[i], wordlist[j]))
for j in xrange(len(wordlist))]
for i in xrange(len(wordlist))]
possible = range(len(wordlist))
n = 0
while possible and n < 6:
guess = solve(H, possible)
n = master.guess(wordlist[guess])
possible = [j for j in possible if H[guess][j] == n]
```

Python:

```# Space: O(n)
class Solution2(object):
def findSecretWord(self, wordlist, master):
"""
:type wordlist: List[Str]
:type master: Master
:rtype: None
"""
def solve(H, possible):
min_max_group, best_guess = possible, None
for guess in possible:
groups = [[] for _ in xrange(7)]
for j in possible:
if j != guess:
groups[H[guess][j]].append(j)
max_group = groups
if len(max_group) < len(min_max_group):
min_max_group, best_guess = max_group, guess
return best_guess

H = [[sum(a == b for a, b in itertools.izip(wordlist[i], wordlist[j]))
for j in xrange(len(wordlist))]
for i in xrange(len(wordlist))]
possible = range(len(wordlist))
n = 0
while possible and n < 6:
guess = solve(H, possible)
n = master.guess(wordlist[guess])
possible = [j for j in possible if H[guess][j] == n]
```

Python:

```def findSecretWord(self, wordlist, master):
n = 0
while n < 6:
count = collections.Counter(w1 for w1, w2 in itertools.permutations(wordlist, 2) if self.match(w1, w2) == 0)
guess = min(wordlist, key=lambda w: count[w])
n = master.guess(guess)
wordlist = [w for w in wordlist if self.match(w, guess) == n]　　```

C++:

```void findSecretWord(vector<string>& wordlist, Master& master) {
for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
unordered_map<string, int> count;
for (string w1 : wordlist)
for (string w2 : wordlist)
if (match(w1, w2) == 0)
count[w1]++;
pair<string, int> minimax = make_pair(wordlist, 1000);
for (string w : wordlist)
if (count[w] <= minimax.second)
minimax = make_pair(w, count[w]);
x = master.guess(minimax.first);
vector<string> wordlist2;
for (string w : wordlist)
if (match(minimax.first, w) == x)
wordlist2.push_back(w);
wordlist = wordlist2;
}
}
```

C++:

```/**
6 / 6 test cases passed.
Status: Accepted
Runtime: 2 ms
*/

class Master {
public:
int guess(string word);
};

class Solution {
public:
int match(const string a, const string b){
int ans = 0;

for(int i = 0;i<a.length(); i++){
if(a[i] == b[i]) ++ans;
}

return ans;
}

void shrinkWordList(vector<string>& wordlits, const string guessWord, const int matches){
vector<string> tmp;

for(string word : wordlits){
int m = match(word, guessWord);
if(m == matches){
tmp.push_back(word);
}
}

wordlits = tmp;
}

void findSecretWord(vector<string>& wordlist, Master& master) {

string target = wordlist[random() % wordlist.size()];
int Count = 10;
while(Count--){
int matches = master.guess(target);

shrinkWordList(wordlist, target, matches);

target = wordlist[random() % wordlist.size()];
}

}
};
```