The "Guess the Word" problem on Leetcode is an interactive problem where you are given a secret word (unknown to you) and a list of possible wordlist candidates. The secret word is guaranteed to be in the list. You can make up to 10 guesses. Each guess must be a word from the wordlist, and you will receive feedback indicating how many letters in your guess match the secret word in both position and value.
Master interface, which exposes a guess(word) method. This method returns an integer: the number of exact positional matches between your guess and the secret word.wordlist.The goal is to design an efficient algorithm to guess the secret word using as few guesses as possible, always within 10 tries.
At first glance, this problem seems to invite a brute-force approach: simply guess words from the list one by one, eliminating words that don't match the feedback. However, with only 10 guesses allowed and potentially hundreds of candidates, this approach is not practical.
The challenge is to maximize the information gained from each guess. The feedback (number of matching positions) allows us to eliminate all words that would not produce the same feedback if they were the secret. Therefore, each guess should be chosen to minimize the worst-case size of the remaining candidate pool, regardless of the feedback received.
This is similar to the game "Mastermind," where each guess should be as "informative" as possible. We need a strategy to select the next guess that splits the remaining candidates as evenly as possible, ensuring that no matter the feedback, the worst-case group is as small as possible.
The optimal solution uses a minimax strategy to select guesses. Here is the step-by-step approach:
This approach helps efficiently narrow down the candidate list and increases the likelihood of finding the secret word within 10 guesses.
Let's walk through an example with a small wordlist and a secret:
wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]secret = "acckzz"At each step, our guess splits the candidate list based on feedback, and we quickly converge on the secret word.
The optimized approach is efficient enough for the typical constraints of the problem.
The "Guess the Word" problem is an exercise in information theory and search optimization. By choosing each guess to minimize the maximum possible size of the remaining candidates (minimax strategy), we efficiently narrow down the possibilities and guarantee finding the secret word within the allowed number of guesses. Key insights include leveraging feedback to filter candidates and using simulation to select the most informative next guess.
class Solution:
def findSecretWord(self, wordlist, master):
def match(w1, w2):
return sum(a == b for a, b in zip(w1, w2))
candidates = wordlist[:]
for _ in range(10):
# Minimax: choose the guess that minimizes the max group size
count = {}
for w in candidates:
m = {}
for x in candidates:
k = match(w, x)
m[k] = m.get(k, 0) + 1
count[w] = max(m.values())
guess = min(count, key=count.get)
matches = master.guess(guess)
if matches == len(guess):
return
candidates = [w for w in candidates if match(guess, w) == matches]
class Solution {
public:
void findSecretWord(vector<string>& wordlist, Master& master) {
auto match = [](const string& a, const string& b) {
int cnt = 0;
for (int i = 0; i < a.size(); ++i)
if (a[i] == b[i]) ++cnt;
return cnt;
};
vector<string> candidates = wordlist;
for (int t = 0; t < 10; ++t) {
unordered_map<string, int> count;
for (const string& w : candidates) {
unordered_map<int, int> m;
for (const string& x : candidates)
++m[match(w, x)];
int mx = 0;
for (auto& p : m)
mx = max(mx, p.second);
count[w] = mx;
}
string guess = min_element(count.begin(), count.end(),
[](const auto& a, const auto& b) { return a.second < b.second; })->first;
int matches = master.guess(guess);
if (matches == guess.size()) return;
vector<string> next;
for (const string& w : candidates)
if (match(guess, w) == matches)
next.push_back(w);
candidates = move(next);
}
}
};class Solution {
public void findSecretWord(String[] wordlist, Master master) {
List<String> candidates = new ArrayList<>(Arrays.asList(wordlist));
for (int t = 0; t < 10; ++t) {
Map<String, Integer> count = new HashMap<>();
for (String w : candidates) {
Map<Integer, Integer> m = new HashMap<>();
for (String x : candidates) {
int k = match(w, x);
m.put(k, m.getOrDefault(k, 0) + 1);
}
int max = 0;
for (int v : m.values()) max = Math.max(max, v);
count.put(w, max);
}
String guess = null;
int min = Integer.MAX_VALUE;
for (String w : count.keySet()) {
if (count.get(w) < min) {
min = count.get(w);
guess = w;
}
}
int matches = master.guess(guess);
if (matches == guess.length()) return;
List<String> next = new ArrayList<>();
for (String w : candidates)
if (match(guess, w) == matches)
next.add(w);
candidates = next;
}
}
private int match(String a, String b) {
int cnt = 0;
for (int i = 0; i < a.length(); ++i)
if (a.charAt(i) == b.charAt(i)) ++cnt;
return cnt;
}
}var findSecretWord = function(wordlist, master) {
function match(a, b) {
let cnt = 0;
for (let i = 0; i < a.length; ++i)
if (a[i] === b[i]) ++cnt;
return cnt;
}
let candidates = wordlist.slice();
for (let t = 0; t < 10; ++t) {
let count = {};
for (let w of candidates) {
let m = {};
for (let x of candidates) {
let k = match(w, x);
m[k] = (m[k] || 0) + 1;
}
count[w] = Math.max(...Object.values(m));
}
let guess = candidates[0];
let min = count[guess];
for (let w in count) {
if (count[w] < min) {
min = count[w];
guess = w;
}
}
let matches = master.guess(guess);
if (matches === guess.length) return;
candidates = candidates.filter(w => match(guess, w) === matches);
}
};