# 843. Guess the Word

### 843. Guess the Word

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++) {
}
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) {