LeetCode 843. 猜猜这个单词

2022-03-11 HGNULB 约 11 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 843. 猜猜这个单词

题意分析

这是一道交互题。系统在给定的单词表里选定了一个秘密单词，我们不能直接读取它，只能调用 master.guess(word)，它返回我们猜的词与秘密词在相同位置上字符相同的个数。所有单词长度固定为 6，词表规模不超过 100。要求在 10 次调用之内至少有一次拿到返回值 6。

「最多 10 次」是最关键的信号。词表最大 100 个词，如果每次随便挑一个猜，最坏要猜 100 次；反过来，允许 10 次说明每一次猜测都必须换来信息量——猜完之后要能砍掉一大批不可能的词。所以这题的本质不是搜索，而是如何选一次能把候选集切得最碎的询问。

还有一个必须先想通的性质：如果我们猜了 g，接口返回 m，那么秘密词 s 一定满足 matchCount(g, s) == m。凡是与 g 匹配数不等于 m 的候选词，都可以立刻永久删除。这个过滤规则是无损的——不会误删真正的答案，因为真正的答案必然满足这个等式。

题目还保证秘密词一定在词表内，这意味着候选集永远非空，也意味着只要每轮都能显著缩小候选集，最终必然收敛到唯一答案。

边界：词表只有一个词时，第一次猜必中；返回值恰好是 6 时要立即停止，否则会继续消耗调用次数甚至猜错；候选集在某轮过滤后如果只剩一个词，下一轮直接猜它即可。

解法：minimax 选词 + 过滤候选（交互策略）

核心思路

先看最朴素的做法：维护候选集合，每次随便取第一个词去猜，然后按返回值过滤。这个做法在最坏情况下极慢——词表里常出现大量两两匹配数为 0 的词，猜中其中一个后返回 0，过滤掉的往往只是与它有公共位置的少数几个，候选集几乎没缩小，10 次远远不够。

瓶颈找到了：随便猜的那一次，返回值的分布极不均匀。绝大部分候选词都会落进「匹配数 = 0」这一个桶里，于是这次询问几乎什么都没学到。

由此得到关键观察：一次猜测 g 会按 matchCount(g, w) 的取值（只可能是 0 到 6 共七种）把当前候选集划分成七个桶。真实返回值落在哪个桶，我们下一轮的候选集就是那个桶。我们无法控制落在哪个桶，只能假设运气最差——落进最大的那个桶。

于是有了 minimax 的评价标准：对每个候选词 g，令 $\text{score}(g) = \max_{0 \le m \le 6} {w \in cand : matchCount(g, w) = m} $，也就是它划分出来的最大桶的大小；我们选择 $\text{score}$ 最小的那个 g 去猜。这一步的语义是「在最坏情况下，让下一轮的候选集尽可能小」。

不变量：每一轮开始时，cand 恰好等于「与目前所有历史询问的返回值都一致的单词集合」，秘密词必定在其中。每轮猜测后按返回值过滤，不变量继续成立，且 |cand| 单调不增。因为选词时最小化了最坏桶，|cand| 会以相当快的速度收缩，实践中远在 10 轮之内就收敛到 1。

猜测的词只从 cand 里取，而不是从原始词表里取。这一点很重要：只有当猜的词本身可能是答案时，才有机会直接命中返回 6 而提前结束；从已被排除的词里挑，即使划分效果更好，也永远没有命中的可能，白白浪费一次机会。

解题步骤

把词表拷进候选集 cand：之后所有过滤都在这个列表上做。用拷贝而不是直接改入参数组，是为了不破坏调用方的数据，也便于每轮整体替换。

最多循环 10 轮：循环条件同时带上 cand 非空，是一层防御——若因为实现错误导致候选集被清空，循环会立刻退出而不是继续调用接口。

选词 pickGuess(cand)：对每个候选 g，开一个长度 7 的桶数组，遍历所有候选 w 统计 matchCount(g, w) 并计数；取桶中最大值作为 g 的分数；扫完取分数最小的词。桶长度取 7 而不是 6，是因为匹配数的取值范围是 0 到 6 共七个值，matchCount(g, g) = 6 也要能放进去。

调用接口并判断命中：match = master.guess(guess)，若等于 6 立刻 return。这个提前返回不是可选的优化——命中之后继续猜会白白消耗剩余次数。

按返回值过滤：新建列表，只保留满足 matchCount(guess, w) == match 的候选，再整体赋回 cand。注意 guess 自己也会被这条规则处理：若 match != 6，matchCount(guess, guess) = 6 != match，它会被自动剔除，不会出现重复猜同一个词的死循环。

以 wordlist = ["abcdef", "abcdeg", "abcdeh", "zzzzzz"] 走一遍，设秘密词是 abcdeh。

第 1 轮，cand 是全部 4 个词。评估 abcdef：它与自己匹配 6，与 abcdeg、abcdeh 各匹配 5，与 zzzzzz 匹配 0，桶为 [1,0,0,0,0,2,1]，最大桶是 2，分数 2。abcdeg、abcdeh 同理也是 2。评估 zzzzzz：与自己匹配 6，与其余三个都匹配 0，桶为 [3,0,0,0,0,0,1]，最大桶 3，分数 3。分数最小的是前三个中最先出现的 abcdef，猜它。

接口返回 5（abcdef 与 abcdeh 前五位相同）。不等于 6，进入过滤：abcdef 与自己匹配 6，剔除；abcdeg 与 abcdef 匹配 5，保留；abcdeh 匹配 5，保留；zzzzzz 匹配 0，剔除。cand 变成 ["abcdeg", "abcdeh"]，一次询问就从 4 个砍到 2 个。

第 2 轮，评估 abcdeg：与自己 6、与 abcdeh 匹配 5，桶 [0,0,0,0,0,1,1]，分数 1；abcdeh 同理分数 1。取先出现的 abcdeg 猜，返回 5，不是 6。过滤后 abcdeg 被自己剔除，只剩 ["abcdeh"]。

第 3 轮，候选唯一，必然猜 abcdeh，返回 6，return。总共 3 次调用，远在 10 次限额之内。

对比一下如果第 1 轮盲选 zzzzzz：返回 0，过滤后剩下三个 abcde?，一次询问只砍掉一个，minimax 的价值就体现在这里。

代码实现

class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        List<String> cand = new ArrayList<>(Arrays.asList(wordlist));
        for (int step = 0; step < 10 && !cand.isEmpty(); step++) {
            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 step := 0; step < 10 && len(cand) > 0; step++ {
        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
}

复杂度分析

时间复杂度：$O(K n^2 L)$，其中 $K \le 10$ 是猜测轮数、$n \le 100$ 是词表大小、$L = 6$ 是词长。每轮选词要对 $n$ 个候选各自与 $n$ 个候选比较一次，单次比较 $O(L)$；过滤只需 $O(nL)$，被选词开销淹没。代入上界约 $10 \times 100^2 \times 6 = 6 \times 10^5$，非常宽松。

空间复杂度：$O(n)$。候选列表与每轮新建的过滤结果各占 $O(n)$，选词时的桶数组固定长度 7 是常数，没有递归栈。

关键点总结

交互题的通用套路是「维护与所有历史反馈一致的候选集合」，每次询问后做无损过滤；先把这个不变量说清楚，再谈选词策略。

询问次数上限就是难度提示：允许的次数远小于候选规模时，一定要求每次询问带走大量信息，而不是逐个试。

minimax 的语义是「在最坏分桶下让下一轮候选最小」，因为我们无法控制接口返回哪个值，只能对最坏情况负责。这是面试时最该讲出来的一句话。

猜测词必须从当前候选集里选，而不是从原始词表里选——只有可能是答案的词才有机会直接命中，否则永远白费一次机会。

过滤规则会顺带把刚猜过的词剔除（它与自己的匹配数是 6，而返回值不是 6），因此不需要额外维护「已猜过」的集合。

面试视角：这题考的是把开放式的「策略设计」翻译成可量化的目标函数。能把「分割效果好」精确成「最大桶最小」，比背下代码更重要。

易错点总结

从原始 wordlist 而不是 cand 里选词：["abcdef","abcdeg","zzzzzz"] 中若第二轮仍从全表选到已被排除的 zzzzzz，这次调用不可能返回 6，10 次限额会被浪费到超限而判错。

命中 6 后不返回：秘密词是 abcdef 时第一次就猜中，若继续循环，过滤后 cand 只剩它自己，会反复对同一个词调用接口，白白耗尽次数甚至触发「超出调用限制」。

桶数组开成长度 6：matchCount(g, g) = 6 会写到下标 6，new int[6] 直接数组越界异常。

过滤条件写成 matchCount(guess, w) >= match：["abcdef","abcdeg","abcdeh"] 秘密词为 abcdeh 时，返回 5 的那轮会把匹配数 6 的 guess 自己留下，导致下一轮重复猜同一个词，陷入原地打转。

bestScore 初值设成 0：任何词的最大桶至少是 1，score < bestScore 永远不成立，最终固定返回 cand.get(0)，退化成盲猜，在两两匹配数为 0 的构造数据上超限。

best 初值不设成 cand.get(0) 而设成 null：若比较写成 score <= bestScore 之外的写法导致一次都没进分支，返回 null 会在调接口时空指针。

匹配数统计写成「字符集合的交集大小」：["abcdef","fedcba"] 这类逆序词，按位置比较是 0，按集合比较是 6，会得出完全错误的过滤结果。题目要的是同位置相同。

过滤时原地在同一个列表上删除元素：Java 中用索引 for 循环边遍历边 remove，会漏检被前移的元素，["a","b","c"] 式的连续剔除只会删掉一半；应当新建列表整体替换。

在 cand 变空后仍调用接口：过滤条件写错导致候选清零时，若循环条件只有轮数，cand.get(0) 会立刻越界；循环条件带上非空判断是廉价的保险。

误以为要返回秘密词：本题方法签名返回 void，正确性由「有没有对秘密词调用过 guess」判定，写 return word 或试图输出结果都是审题错误。

相似题目

题目	难度	考察点
374. 猜数字大小	简单	同为交互题，但反馈是有序的大小关系，二分即可，无需分桶
299. 猜数字游戏	中等	只考本题里 `matchCount` 那一步，还要额外统计位置不对的「奶牛」数
278. 第一个错误的版本	简单	交互接口返回布尔值，答案具单调性，考的是二分边界而非信息量最大化
1178. 猜字谜	困难	同样是词与词的匹配统计，但用状态压缩枚举子集，离线批量回答
486. 预测赢家	中等	minimax 的经典 DP 形态：对手最优应对下的最坏收益，本题是其贪心近似
464. 我能赢吗	中等	状态压缩记忆化搜索的博弈，考的是必胜态推导而非缩小候选集
877. 石子游戏	中等	区间 DP 求先手最优差值，也可用奇偶性一句话结论秒杀
292. Nim 游戏	简单	博弈论中直接给出必败态公式的极简例子，用来对照「有无策略搜索」