# Guess the Word

**Hard**

This problem is an ***interactive problem*** new to the LeetCode platform.

We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as **secret**.

You may call`master.guess(word)` to guess a word. The guessed word should have type`string` and must be from the original list with 6 lowercase letters.

This function returns an `integer` type, representing the number of exact matches (value and position) of your guess to the **secret word**. Also, if your guess is not in the given wordlist, it will return`-1`instead.

For each test case, you have 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or less calls to`master.guess` and at least one of these guesses was the **secret**, you pass the testcase.

Besides the example test case below, there will be 5 additional test cases, each with 100 words in the word list. The letters of each word in those testcases were chosen independently at random from`'a'`to`'z'`, such that every word in the given word lists is unique.

```
Example 1:
Input:
 secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]


Explanation:
master.guess("aaaaaa")
 returns -1, because 
"aaaaaa"
 is not in wordlist.

master.guess("acckzz") 
returns 6, because 
"acckzz"
 is secret and has all 6 matches.

master.guess("ccbazz")
 returns 3, because
 "ccbazz"
 has 3 matches.

master.guess("eiowzz")
 returns 2, because 
"eiowzz"
 has 2 matches.

master.guess("abcczz")
 returns 4, because 
"abcczz"
 has 4 matches.

We made 5 calls to master.guess and one of them was the secret, so we pass the test case.
```

**Note:** Any solutions that attempt to circumvent the judge will result in disqualification.

## Solution

### 直觉想法：

1.在wordlist中随机选一个数字猜，得到match的数目；

2.在wordlist找到有相同match数的word，组成新的列表；

3.重复以上步骤，直到match数为6，说明猜到了secret；或者超出猜的次数10次

下面的代码大概有30\~50%的几率能通过LeetCode的OJ。因此还需要改进。

```java
/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface Master {
 *     public int guess(String word) {}
 * }
 */
class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
            String guess = wordlist[new Random().nextInt(wordlist.length)];
            x = master.guess(guess);
            List < String > wordlist2 = new ArrayList<>();
            for (String w: wordlist) {
                if (match(guess, w) == x) {
                    wordlist2.add(w);
                }
            }
            wordlist = wordlist2.toArray(new String[wordlist2.size()]);
        }
    }
    public int match(String a, String b) {
        int matches = 0;
        for (int i = 0; i < a.length(); ++i) {
            if (a.charAt(i) == b.charAt(i)) {
                matches++;
            }
        }
        return matches;
    }
}
```

### 改进 Minimax：

可以通过剪枝来缩小初始的搜索范围。对所有字符串进行两两匹配，如果得0就存入hashmap `count`。最后选取匹配度为0的最少的字符串，然后在进行以上操作。

> Generally, we will get 0 matches and wordlist size reduce slowly.

对于word两两匹配寻找0 match的解释：

> Anyone who doesn't know `why checking 0 match` instead of 1,2,3...6 matches, please take a look at this comment. The probability of two words with 0 match is (25/26)^6 = 80%. That is to say, for a candidate word, we have 80% chance to see 0 match with the secret word. In this case, we had 80% chance to eliminate the candidate word and its "family" words which have at least 1 match. Additionally, in order to delete a max part of words, we select a candidate who has a big "family" (fewest 0 match with other words).

简单来说，就是因为每次我们都是先得到一个word和secret之间的match数x，再去wordlist找match数为x的word作为潜在的候选词，但是，随机猜词有很大的概率得到的match数x = 0，因为有大约80%概率（计算：(25/26) ^ 6 \~ 80%）。如果通过match为0，再去寻找候选词，那么有很大可能，新的wordlist中词数并没有减少很多。

至于为什么从两两match为0的词中选择0 match次数最少的呢？也是同样道理，因为无论怎么选，通过master.guess(candidate)返回的match值大概率都是0，那么最有意义的就是通过candidate，来寻找wordlist中有match值为0，这样就大大加快了缩小搜索范围的速度。

```java
import javafx.util.Pair;
/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface Master {
 *     public int guess(String word) {}
 * }
 */
class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
            HashMap<String, Integer> count = new HashMap<>();
            for (String w1: wordlist) {
                for (String w2 : wordlist) {
                    if (match(w1, w2) == 0) {
                        count.put(w1, count.getOrDefault(w1, 0) + 1);
                    }
                }
            }

            Pair<String, Integer> minimax = new Pair<>("", 1000);
            for (String w : wordlist) {
                if (count.getOrDefault(w, 0) < minimax.getValue()) {
                    minimax = new Pair<>(w, count.getOrDefault(w, 0));
                }
            }

            String guess = minimax.getKey();
            x = master.guess(guess);
            List < String > wordlist2 = new ArrayList < > ();
            for (String w: wordlist) {
                if (match(guess, w) == x) {
                    wordlist2.add(w);
                }
            }
            wordlist = wordlist2.toArray(new String[wordlist2.size()]);
        }
    }
    public int match(String a, String b) {
        int matches = 0;
        for (int i = 0; i < a.length(); ++i) {
            if (a.charAt(i) == b.charAt(i)) {
                matches++;
            }
        }
        return matches;
    }
}
```

## Reference

<https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison>

<https://leetcode.com/problems/guess-the-word/discuss/164744/Logical-Thinking-Exclude-the-Impossible>