[LeetCode] 843. Guess the Word

[grandyang]

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.

这道题号称是 LeetCode 平台上第一个交互式的题目，但定睛一看，踩比赞多，哎，创新不易啊～ 这道题说是有一个单词数组 wordlist，其中有一个单词是需要被猜到的单词 secret，现在有一个 api 函数 guess，可以返回猜的单词和目标单词之间的匹配个数。现在每个 test case 有 10 次机会去猜目标单词，假如调用 api 的次数不超过 10 次，并猜中了目标单词的话，就可以通过测试。首先，由于需要尽可能少的调用 api，所以线性的一个一个的对每个单词调用 api 是不可取的，因为假如目标单词在最后一个，且单词数组长度超过 10 个，就会失败。这样的话可以随机取一个单词来检测，调用 api 后会得到一个次数 cnt，表示当前单词和目标单词之间的匹配个数。接下来怎么办呢？需要过滤一遍单词数组，自己写一个类似于 api 的函数，返回任意两个单词之间的匹配个数，这样就可以 filter 整个单词数组了，因为藏在普通单词中的目标单词跟当前单词调用 match 函数的返回值一定还是 cnt，当然也会有其他的单词同样返回 cnt，不过没关系，还是能滤去一大波不相干的单词，重复这个步骤，直到 cnt 正好为6停止，因为题目中说了单词的长度就是6，参见代码如下：

class Solution {
public:
    void findSecretWord(vector<string>& wordlist, Master& master) {
        for (int i = 0, cnt = 0; i < 10 && cnt < 6; ++i) {
        	string guess = wordlist[rand()  % (wordlist.size())];
        	cnt = master.guess(guess);
        	vector<string> t;
        	for (string &word : wordlist) {
        		if (match(guess, word) == cnt) {
        			t.push_back(word);
        		}
        	}
        	wordlist = t;
        }
    }
    int match(string& a, string& b) {
    	int res = 0, n = a.size();
    	for (int i = 0; i < n; ++i) {
    		if (a[i] == b[i]) ++res;
    	}
    	return res;
    }
};

Github 同步地址:

#843

参考资料：

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

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

https://leetcode.com/problems/guess-the-word/discuss/134251/Optimal-MinMax-Solution-(%2B-extra-challenging-test-cases)

LeetCode All in One 题目讲解汇总(持续更新中...)