猜词游戏-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

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

思路：

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

代码：

```java
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;
        }
    }
}
```

该分类下的相关小册推荐：

业务开发实用算法精讲

数据结构与算法(下)

编程之道-算法面试(下)

编程之道-算法面试(上)

数据结构与算法之美

算法面试通关 50 讲

数据结构与算法(上)