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 callmaster.guess(word) to guess a word. The guessed word should have typestring 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-1instead.

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 tomaster.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。因此还需要改进。

/**
 * // 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，这样就大大加快了缩小搜索范围的速度。

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