843[H]. Guess the word

https://leetcode-cn.com/problems/guess-the-word

现有网络上的的几个题解在极小化极大这个关键之处都一语带过，能找到的基本上最清晰的解释还是在这里

基本思路

基本思路其实很简单：每次猜一个单词，根据匹配的情况从候选词列表筛除掉一部分，重复直到猜到正确的单词。

这里用到了一个重要的推论：因为 secret 单词就在候选词列表中，所以如果猜的单词 guess 和 secret 匹配度（对应正确字母的数量）是 N 的话，那么候选词中所有跟 guess 这个单词的匹配度为 N 的单词集合，必然包含 secret。

那么，如何判断每次猜测的时候选择哪一个单词呢？这才是这个题目最重要的点。

有很多个方案可以选择

1. 每次都选择候选词里的第一个

2. 每次从候选词里面随机选一个

3. 按照某种规则选择一个

第一个方案和第二个方案的效果基本差不多，实测在 10000 个随机生成的候选词中，差不多 10 次左右就能得到答案，当然也有不少 12、13 次才能得到答案的情况。那么就来看看第三种方案效果如何。

极大极小化

我们尝试寻找一个规则，使得每次选择之后的候选词集合尽可能的小（这样更快的让候选词集合变小，更快的得到答案）。

先做一个简单的计算，随机猜测一个 6 个字母的单词，完全没有猜中的可能性有多大？单词有 6 个字母，每个字母猜错的可能是 25/26，所以 6 个字母都猜错的可能性是

$$(\frac{25}{26})^6 ≈ 0.79031$$

(25/26)^ ≈ 0.79031 。也就是每猜一次大约有 80% 的可能性一个字母都没有命中，这是最坏的一种情况。我们姑且称之为匹配度，两个单词匹配度为 1 表示这两个单词在对应的位置上只有 1 个字母是相同的（譬如 abc 和 axy，abc 和 cba 的匹配度都是 1）。

举一个实测的例子，10000 个随机候选词，随机选其中一个单词，这个单词跟其它候选词的匹配度大概是这样一个分布 7971, 1834, 180, 14, 1, 0, 0 ，我们姑且称之为“匹配度数组”，表示这个单词与其它所有候选词的匹配情况。前面这个例子中，匹配度为 0 的有 7971个，匹配度为 1 的有 1834个，以此类推。我们可以看到，**目前**可能出现的最坏的情况是匹配度为 0 的那一组，有 7971 个单词跟所选的单词没有一个字母重合。

假如能猜测的单词能命中一个字母的话，那么很好，这一下至少可以排除掉 80% 的候选词了。但是这个是我们无法控制的，最坏的情况下还是可能会命中那 80% 的情况。我们能做的就是，尽可能的让最坏的情况变得好一点。也就是让匹配度数量最多的那一组的单词数量越小越好。

譬如在前述的 10000 个候选词中，我随机选择了 10 个单词，去计算每一个单词与剩下的候选词的匹配度，匹配度的分布大约是

7971, 1834, 180, 14, 1, 0, 0
7911, 1897, 180, 12, 0, 0, 0
7797, 2000, 190, 13, 0, 0, 0
7912, 1893, 185, 10, 0, 0, 0
7868, 1942, 180, 9, 1, 0, 0
7943, 1841, 203, 13, 0, 0, 0
7865, 1929, 194, 11, 1, 0, 0
7978, 1830, 182, 10, 0, 0, 0
7942, 1851, 202, 5, 0, 0, 0
7887, 1925, 176, 11, 1, 0, 0

假如要在这 10 个单词里面选一个，我当然要选第 3 个，因为选择第 3 个在出现最坏的情况——也就是一个字母都没命中的情况——它下一步的候选词数量最少，只有 7797 个。如果出现其它情况，那非常好，这 7797 个和其它剩余的 5 组一下就可以都排除掉了，这是比更加理想的结果。而在最坏情况下，至少能保证结果相对来说比选择第 8 个或者其它的单词要好，第 8 个单词在最坏情况下候选词有 7978 个，这个更差。

而实际上我们需要在整个候选词列表中选择一个，那么方案就很明显了，遍历候选词列表，判断所有候选词与其他候选词的匹配度，选择在可能出现的最坏的情况下的表现最好的那个单词。

这句话稍有点绕，可能出现的“最坏的情况”指的是数量最多的那个匹配度（目前是 0），而“表现最好”指的是所有候选词中，这个匹配度（目前是 0）单词数量最少的那个单词。这就是所谓的极小化极大，“极大”指的是找到最坏情况，“极小化”指的是让最坏情况下的候选词数量极小。

在前面反复说的“可能出现的最坏情况”一直是假设匹配度为 0 的情况。但实际情况也并不一定总是如此，譬如所有单词都有一个共同的前缀或者后缀，那么所有的单词的匹配度都至少是 1，也就是说“可能出现的最坏情况”其实是匹配度为 1 的情况。

所以实际在判断“可能出现的最坏情况”的时候，我们要从一个单词的匹配度数组中找到最大的那个数值，这个数值表示的是对应匹配度的候选词个数，我们其实并不需要关心具体的匹配度是多少，而只关心对应的候选词个数。因为其它数值更小的表示更小的单词集合，那么在命中这种情况的时候，下一次的候选词集合就更少，这是相对较好的情况而不是最坏的情况。

这个算法，时间复杂度 O(n^2)，空间复杂度 O(n)

class Solution {
    fun getMatchCount(a: String, b: String): Int {
        var res = 0
        for (i in a.indices) {
            if (a[i] == b[i]) {
                res++
            }
        }
        return res
    }

    fun buildMatches(wordList: Array<String>): Array<IntArray> {
        val size = wordList.size
        val matches = Array(wordList.size) { IntArray(wordList.size) { 0 } }
        for (i in 0 until size) {
            for (j in i until size) {
                matches[i][j] = getMatchCount(wordList[i], wordList[j])
                matches[j][i] = matches[i][j]
            }
        }
        return matches
    }

    fun findGuess(candidates: List<Int>, matches: Array<IntArray>): Int {
        var maxSize = Int.MAX_VALUE
        var guess = -1
        for (i in candidates) {
            val groups = IntArray(7) { 0 }
            for (j in candidates) {
                if (i != j) {
                    groups[matches[i][j]]++
                }
            }
            val currentMax = groups.max()!!
            if (currentMax < maxSize) {
                guess = i
                maxSize = currentMax
            }
        }
        return guess
    }

    fun findSecretWord(wordList: Array<String>, master: Master) {
        val matches = buildMatches(wordList)

        var candidates = wordList.indices.toList()
        var times = 0
        while (candidates.isNotEmpty()) {
            times += 1
            val guess = findGuess(candidates, matches)
            val match = master.guess(wordList[guess])
            if (match == 6) {
                // println("secret is ${wordList[guess]}")
                return
            }

            candidates = candidates.filter { matches[guess][it] == match }
        }
    }
}

以上。