LeetCode 843. 猜猜这个单词
题目描述
题意分析
列表中的单词互不相同且长度都为 6，秘密词一定在其中。每次必须用原列表中的词调用
Master.guess，返回与秘密词在相同位置相同字符的数量；返回 6 才算实际猜中。每个用例的allowedGuesses在 10 到 30 之间，必须在对应额度内命中。
解法：候选分桶 + 反馈筛选
核心思路
[!blue]
用
cand保存与此前所有反馈一致、仍可能是秘密词的单词，初始为完整列表。若本轮猜g得到反馈m，真实答案一定满足matchCount(g, w) = m，所以只保留这一类候选。旧集合已经符合过去的反馈，再与本次条件取交集，就能持续缩小范围而不误删真实答案。还需要决定猜哪个词。对于候选
g，把所有当前候选按它们与g的位置匹配数0..6分成七个桶。实际反馈会指出秘密词属于哪个桶，未命中时就只能留下相应桶；因此用最大桶大小衡量这次猜测最坏会留下多少可能性，再选择这个数最小的词。代码只从当前候选中选择猜词，所以猜测始终属于原列表，也保留直接命中的机会。自匹配结果为 6，桶数组必须有七项。若反馈不是 6，刚猜过的词就不会通过精确筛选，候选数至少减少一；若反馈为 6，立即结束。即使只剩一个候选，也必须实际调用查询，不能只推断出答案就返回。
精确筛选的正确性与选词策略的效果需要区分。最大桶最小只优化本轮的最坏剩余规模，不是在搜索完整的最优决策树，也不能保证每轮减半。题目接口没有传入查询额度，代码不写死十轮，而是继续筛选直到命中；这仍需依赖策略在用例额度内猜中，不能将候选最终会减少完等同于查询次数一定合格。
解题步骤
- 用全部单词初始化候选集合。
- 对每个可猜词统计七个反馈桶，选择最大桶最小者。
- 调用查询，返回六则立即结束。
- 仅保留与本轮反馈一致的词，继续选词。
代码实现
class Solution {
public void findSecretWord(String[] wordlist, Master master) {
List<String> cand = new ArrayList<>(Arrays.asList(wordlist));
while (!cand.isEmpty()) {
String guess = pickGuess(cand);
int match = master.guess(guess);
// 查询返回六才表示实际猜中，立即结束交互。
if (match == 6) {
return;
}
List<String> next = new ArrayList<>();
for (String w : cand) {
// 只保留与本轮实际反馈完全一致的候选，真实答案不会被排除。
if (matchCount(guess, w) == match) {
next.add(w);
}
}
cand = next;
}
}
private String pickGuess(List<String> cand) {
int bestScore = Integer.MAX_VALUE;
String best = cand.get(0);
for (String g : cand) {
// 反馈范围包含零到六，自匹配的六也需要一个桶。
int[] buckets = new int[7];
for (String w : cand) {
int m = matchCount(g, w);
buckets[m]++;
}
int score = 0;
for (int x : buckets) {
score = Math.max(score, x);
}
// 选择最大反馈桶最小的候选，优化本轮最坏剩余规模。
if (score < bestScore) {
bestScore = score;
best = g;
}
}
return best;
}
private int matchCount(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;
}
}
func findSecretWord(wordlist []string, master *Master) {
cand := make([]string, 0, len(wordlist))
cand = append(cand, wordlist...)
for len(cand) > 0 {
guess := pickGuess(cand)
match := master.Guess(guess)
// 查询返回六才表示实际猜中，立即结束交互。
if match == 6 {
return
}
next := make([]string, 0, len(cand))
for _, w := range cand {
// 只保留与本轮实际反馈完全一致的候选，真实答案不会被排除。
if matchCount(guess, w) == match {
next = append(next, w)
}
}
cand = next
}
}
func pickGuess(cand []string) string {
bestScore := 1<<31 - 1
best := cand[0]
for _, g := range cand {
// 反馈范围包含零到六，自匹配的六也需要一个桶。
buckets := make([]int, 7)
for _, w := range cand {
buckets[matchCount(g, w)]++
}
score := 0
for _, x := range buckets {
if x > score {
score = x
}
}
// 选择最大反馈桶最小的候选，优化本轮最坏剩余规模。
if score < bestScore {
bestScore = score
best = g
}
}
return best
}
func matchCount(a, b string) int {
cnt := 0
for i := 0; i < len(a); i++ {
if a[i] == b[i] {
cnt++
}
}
return cnt
}
复杂度分析
- 时间复杂度：设实际查询轮数为 Q、最多候选数为 N、词长为 L，时间上界 $O(QN^2L)$；本题 L 固定为六。
- 空间复杂度：$O(N)$，前后候选列表及固定七桶。
关键点总结
[!green]
- 匹配按相同位置计算，不是字符集合交集。
- 每轮候选都要满足此前全部反馈。
- 返回六表示真正命中，不能只推断候选唯一而不调用查询。
易错点总结
[!yellow]
- 反馈过滤使用大于等于：保留与真实结果矛盾的词，可能重复猜测。
- 桶数组只开六项：自匹配结果六会越界。
- 只比较包含哪些字母：相同字母位于不同位置时不能算匹配。
- 把最大桶最小误当作每轮减半保证：局部策略没有这样的固定收缩比例。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 299. 猜数字游戏 | 中等 | 同样用位置匹配数衡量猜测，本题只返回位置命中数，并据此排除不可能的秘密词。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！