843. Guess the Word

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

给定一组单词，每个单词长度为6，让猜其中一个被选中的，调用guess(w)会返回w和target完全相同字符数目，要求10词内猜中。要尽量每次调用guess后大幅降低问题空间，guess返回了与target相同字符数，因此可以此为筛选标准。每次随机选一个作为候选，调用guess得到返回值ret，然后找当前wordlist中与候选相同字符数刚好是ret作为新的wordlist，依此类推。

参考自这。

/*
 * @lc app=leetcode id=843 lang=cpp
 *
 * [843] Guess the Word
 *
 * https://leetcode.com/problems/guess-the-word/description/
 *
 * algorithms
 * Hard (44.44%)
 * Likes:    330
 * Dislikes: 358
 * Total Accepted:    27.1K
 * Total Submissions: 60.5K
 * Testcase Example:  '"acckzz"\n["acckzz","ccbazz","eiowzz","abcczz"]\n10'
 *
 * 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.
 * 
 */

// @lc code=start
/**
 * // 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) {
        const auto match = [](string &a, string &b) {
            int res = 0;
            for (int i = 0; i < a.length(); ++i) {
                if (a[i] == b[i]) ++res;
            }
            return res;
        };
        for (int i = 0, cnt = 0; i < 10 && cnt < 6; ++i) {
            string candidate = wordlist[rand() % wordlist.size()];
            cnt = master.guess(candidate);
            vector<string> ws;
            for (auto w : wordlist) {
                if (match(w, candidate) == cnt) {
                    ws.push_back(w);
                } 
            }
            wordlist = ws;
        }
    }
};
// @lc code=end