[LeetCode]Guess the Word

这道题是猜数字的游戏，通常这类题目我们仍然是运用minimax的思路，对于所有可能成为答案的candidates：

• 对于每一个数，我们要算其在所有match可能(0-5)下，能eliminate的最少数量，我们称其为这个pick的score。考虑最坏的情况，这就是min
• 那么对于所有可能pick的数，我们取score最大的。在所有可选的范围内选择最优的，这就是max

我们需要preprocess建立一个match的表，维护了每两个string match的情况。然后对于每一个可能的pick，和match数m，我们计算其可以排除掉的数，即如果string和pick的match数不为m，那么肯定不是当前条件的答案的候选，所以排除。时间复杂度O(N^2 * log N)，每一次pick的过程是O(N^2)，每次应该pick之后至少应该能排除一半，所以是log N，代码如下：

	/*
	* class Master {
	* public:
	* int guess(string word);
	* };
	*/
	class Solution {
	public:
	void findSecretWord(vector<string>& wordlist, Master& master) {
	int len = wordlist.size();
	vector<vector<int>> matches(len, vector<int>(len, 0));
	for(int i = 0; i < len; ++i)
	{
	matches[i][i] = 6;
	for(int j = i + 1; j < len; ++j)
	{
	matches[i][j] = match(wordlist[i], wordlist[j]);
	matches[j][i] = matches[i][j];
	}
	}
	vector<int> cands;
	for(int i = 0; i < len; ++i)cands.push_back(i);
	while(cands.size())
	{
	int idx = pick(cands, matches);
	int matchedChars = master.guess(wordlist[cands[idx]]);
	if(matchedChars == 6)return;
	vector<int> tmp;
	for(int i = 0; i < cands.size(); ++i)
	if(matches[cands[idx]][cands[i]] == matchedChars)tmp.push_back(cands[i]);
	cands = tmp;
	}
	}
	private:
	int match(string& lhs, string& rhs)
	{
	int cnt = 0;
	for(int i = 0; i < 6; ++i)
	if(lhs[i] == rhs[i])++cnt;
	return cnt;
	}
	int pick(vector<int>& cands, vector<vector<int>>& matches)
	{
	int idx = -1, groupSize = INT_MAX;
	for(int i = 0; i < cands.size(); ++i)
	{
	vector<int> cnts(7);
	for(int j = 0; j < cands.size(); ++j)
	{
	if(j != i)
	++cnts[matches[cands[i]][cands[j]]];
	}
	int maxSize = 0;
	for(auto& cnt : cnts)if(cnt > maxSize)maxSize = cnt;
	if(maxSize < groupSize)
	{
	groupSize = maxSize;
	idx = i;
	}
	}
	return idx;
	}
	};

view raw Guess the Word.cpp hosted with ❤ by GitHub