843. Guess the Word

方法1: brute forceComplexity 方法2: minimax heuristicComplexity 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.

方法1: brute force

思路：

首先采用最自然的strategy，随便选一个词猜，获得反馈match，那么我们可以排除所有和这个词match不等于这个反馈的值，去掉他们。再次随机一个单词，循环直至猜中。

随机选词不但过了，还挺快的。

Complexity

Time complexity: O(n) Space complexity: O(n)

/** * // This is the Master's API interface. * // You should not implement it, or speculate about its implementation * class Master { * public: * int guess(string word); * }; */ class Solution { public: void findSecretWord(vector<string>& wordlist, Master& master) { int match = 0; for (int i = 0; i < 10, match < 6; i++) { int guess_id = rand() % wordlist.size(); match = master.guess(wordlist[guess_id]); reduceWordList(wordlist, match, wordlist[guess_id]); } } void reduceWordList(vector<string>& wordlist, int match, string cur) { vector<string> newWordList; for (int i = 0; i < wordlist.size(); i++) { if (isMatch(wordlist[i], cur, match)) { newWordList.push_back(wordlist[i]); } } wordlist = newWordList; } bool isMatch(string a, string b, int match) { int cnt = 0; if (a.size() != b.size()) { return false; } for (int i = 0; i < a.size(); i++) { if (a[i] == b[i]) { cnt++; } } return cnt == match; } };

方法2: minimax heuristic

_pzh: https://leetcode.com/problems/guess-the-word/discuss/134251/Optimal-MinMax-Solution-(+-extra-challenging-test-cases) lee215: https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison

思路：

根据上面的思路，每次我们都根据得到的match来删除一部分单词，所以我们应该尽量maximize每次能去掉的单词数。第一个帖子指出，我们需要每次在（原）单词列表中找一个单词，计算pairwise的单词match，并且统计histogram 中的峰值，这个峰值就是选该单词后worst case我们会剩下的单词数量。因此用minimax的思想，我们选择在所有单词中这个peak最小的那个词，这代表该单词可以尽量均匀的partition wordlist。而第二个帖子指出，经过统计大部分的单词之间都是0重叠，所以不用每次都统计histogram了，直接heuristicly的选出与其他单词match = 0 最少的那个单词去猜就可以。

Complexity

Time complexity: O(n^2) Space complexity: O(n)

第一帖：

class Solution { int dist(const string& a, const string &b) { // Maybe this can be memoized if too slow. int dist = 0; for (int idx = 0; idx < a.size(); ++idx) { dist += a[idx] == b[idx]; } return dist; } int maxEquidistantSetSize(const string& word, const unordered_set<string>& guessSet) { vector<int> hist(word.size() + 1, 0); for (auto& guess : guessSet) { ++hist[dist(word, guess)]; } return *max_element(hist.cbegin(), hist.cend()); } string maxPartitioningGuess(const vector<string>& wordlist, const unordered_set<string>& guessSet) { auto maxGuessIt = wordlist.cend(); int minMax = wordlist.size(); for (auto it = wordlist.cbegin(); it != wordlist.cend(); ++it) { int curMax = maxEquidistantSetSize(*it, guessSet); if (curMax < minMax) { minMax = curMax; maxGuessIt = it; } } return *maxGuessIt; } public: void findSecretWord(vector<string>& wordlist, Master& master) { // Start guessing unordered_set<string> guessSet(wordlist.cbegin(), wordlist.cend()); while (guessSet.size() > 1) { // Calculate max partitioning elem taken from full word list string guessWord = maxPartitioningGuess(wordlist, guessSet); // Try the guess int d = master.guess(guessWord); if (d == guessWord.size()) return; // Got lucky! // Eliminate words whose distance != d for (auto it = guessSet.begin(); it != guessSet.end();) { if (dist(guessWord, *it) != d) { it = guessSet.erase(it); } else { ++it; } } } if (!guessSet.empty()) { master.guess(*guessSet.cbegin()); } } };

第二贴：

void findSecretWord(vector<string>& wordlist, Master& master) { for (int i = 0, x = 0; i < 10 && x < 6; ++i) { unordered_map<string, int> count; for (string w1 : wordlist) for (string w2 : wordlist) if (match(w1, w2) == 0) count[w1]++; pair<string, int> minimax = make_pair(wordlist[0], 1000); for (string w : wordlist) if (count[w] <= minimax.second) minimax = make_pair(w, count[w]); x = master.guess(minimax.first); vector<string> wordlist2; for (string w : wordlist) if (match(minimax.first, w) == x) wordlist2.push_back(w); wordlist = wordlist2; } }