高频题？ 这题怎么做：Leetcode 843. Guess the Word

https://leetcode.com/problems/guess-the-word/

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.

aaaaaa
aaaaab
aaaaac
aaaaad
.
.
.
aaaaaz
這種測資保證你10次猜不出來
什麼怪題目

看discuss啊，discuss里的最高票说的很明白啊

提供一种可以通过的做法，每次随机一个word，得到master匹配的结果match，然后和当前剩余的所有word匹配把结果不等于match的删掉，以此循环。
然后看了一下题解，思路总体方向一致，但是题解在单词选择上有一个策略，每次选择word不是随机选择而是选择能够尽可能排除掉不可能的候选项的word。

1. class Solution {
   
2. public:
   
3.     void findSecretWord(vector<string>& wordlist, Master& master) {
   
4.         int n = wordlist.size();
   
5.         unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
   
6.         vector<string> new_list;
   
7.         auto old_list = wordlist;
   
8.         for (int i = 0; i < 10; ++i) {
   
9.             shuffle(old_list.begin(), old_list.end(), default_random_engine(seed));
   
10.             auto match = master.guess(old_list[0]);
    
11.             for (auto s : old_list) {
    
12.                 if (compare(s, old_list[0]) == match) {
    
13.                     new_list.push_back(s);
    
14.                 }
    
15.             }
    
16.             old_list = new_list;
    
17.             new_list.clear();
    
18.         }
    
19.     }
    
20.     int compare(const string& s1, const string& s2) {
    
21.         int cnt = 0;
    
22.         for (size_t i = 0; i < min(s1.size(), s2.size()); ++i) {
    
23.             if (s1[i] == s2[i]) cnt++;
    
24.         }
    
25.         return cnt;
    
26.     }
    
27. };

复制代码

我的大概思路是，
1）先随机从input list挑一个字符串 然后guess一下看看有多少位是match的，如果返回0就重复这一步直到返回大于0，每次guess完把这个字符串从list里去掉
2）compare 刚才的字符串和 list里剩下的字符串，把所有跟刚才的字符串相match的位跟第一步的返回值相同的字符串加到一个新的list里去
3）然后更新input成刚才做出来的那个list

听说airbnb面经也有个guess word, 和LC的不一样。请问哪位能描述下airbnb那题具体是什么?

我前两天google onsite遇到的就是个题的变形，改的稍微难了一点，但是大致一样。
有一个follow up，如何选择第一个guess。
我当时思路就是高票的那个，但是最后一步，update candidate words list那里写错了，也侥幸过了HC。
仅供参考。

https://leetcode.com/articles/guess-the-word/

发帖不留名 发表于 2019-5-27 21:14
看discuss啊，discuss里的最高票说的很明白啊

第一次知道有vote，感谢你的评论。