[数据结构与算法]【Leetcode】843. Guess the Word

题目地址：

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

给定一个长$n$的字符串数组$A$，只含英文小写字母，并且每个字符串长度相等，都是$l$。现在要猜单词，给定一个类，输入是长$l$的字符串，输出是该字符串与要猜的单词有几个位置是正确的。总共猜$10$次，设计算法去猜单词（不一定要求猜中，但要最大可能性去争取猜中）。

先存一下数组$f[i][j]$，表示$A[i]$和$A[j]$有几个位置是相等的。那么当我们猜单词的，我们尽量选那些如果猜错了，就能删掉最多单词的那个单词，那么可以先枚举一下每个单词，有多少个单词与之有$0,1,...,6$个位置不同，然后取最大，那么如果这个单词不是要猜的单词，能删掉的单词是最多的（如果当前猜的单词$s$位置正确的有$k$位，那么就筛选出$k$位与$s$相同的字符串作为候选即可）。代码如下：

public class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        int n = wordlist.length;
        int[][] f = new int[n][n];
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 6; k++) {
                    if (wordlist[i].charAt(k) == wordlist[j].charAt(k)) {
                        f[i][j]++;
                    }
                }
            }
        }
        
        for (int i = 0; i < 10; i++) {
            int k = -1, w = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (vis[j]) {
                    continue;
                }
                
                int t = 0;
                for (int u = 0; u <= 6; u++) {
                    t = Math.max(t, get(j, u, n, vis, f));
                }
                
                if (w > t) {
                    k = j;
                    w = t;
                }
            }
            
            int res = master.guess(wordlist[k]);
            if (res == 6) {
                break;
            }
            
            vis[k] = true;
            for (int j = 0; j < n; j++) {
                if (f[k][j] != res) {
                    vis[j] = true;
                }
            }
        }
    }
    
    int get(int j, int u, int n, boolean[] vis, int[][] f) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i] && f[j][i] == u) {
                res++;
            }
        }
        
        return res;
    }
}

interface Master {
    int guess(String word);
}

时空复杂度$O(n^2)$。