# 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 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 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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/company-tag/google/guess-the-word.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.