Skip to content

843. Guess the Word

843. Guess the Word

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

难度: Hard

题意：

  1. 给定最多100个长度为6的字符串
  2. 有一个字符串为秘密字符串，需要从这些字符串中猜出秘密字符串是哪个
  3. 每一轮猜会给出你猜的跟秘密字符串的不同字符数
  4. 最多猜10轮

思路：

  • 这个题就纯模拟，挑一个字符串，然后根据返回的数，来决定下一轮的备选字符串
  • 加快速度的话，可以枚举所有的字符串，判断这个字符串跟其他字符串的字符差的统计值，取统计值差异最大的字符串来作为这一轮的猜测
  • 类似决策树

代码：

class Solution {
     private int calDiff(String word1, String word2) {
        int ret = 0;
        for (int i = 0;i < word1.length();i++) {
            if (word1.charAt(i) == word2.charAt(i)) {
                ret++;
            }
        }
        return ret;
    }

    private int select(int idx, List<Integer> pre, int[][] cache) {
        int[] dist = new int[7];
        Arrays.fill(dist, 0);
        for (int x: pre) {
            dist[cache[idx][x]] ++;
        }
        int ret = 0;
        for (int i = 0;i < 6;i++) {
            ret = Math.max(ret, dist[i]);
        }
        return ret;
    }

    private int select(List<Integer> pre, int[][] cache) {
        int value = 1000000;
        int ret = -1;
        for (int idx: pre) {
            int tmp = select(idx, pre, cache);
            if (tmp < value) {
                value = tmp;
                ret = idx;
            }
        }
        return ret;
    }

    public void findSecretWord(String[] wordlist, Master master) {
        int[][] cache = new int[wordlist.length][wordlist.length];
        for (int i = 0;i < wordlist.length;i++) {
            for (int j = 0;j < wordlist.length;j++) {
                cache[i][j] = calDiff(wordlist[i], wordlist[j]);
            }
        }

        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0;i < wordlist.length;i++) {
            pre.add(i);
        }
        while (pre.size() != 0) {
            int first = select(pre, cache);

            int diff = master.guess(wordlist[first]);
            if (diff == 6) {
                return;
            }
            List<Integer> post = new ArrayList<Integer>();
            for (int x: pre) {
                if (cache[first][x] == diff) {
                    post.add(x);
                }
            }
            pre = post;
        }
    }
}
回到顶部