【博弈】843. 猜猜这个单词

本题涉及知识点

博弈

LeetCode843. 猜猜这个单词

给你一个由不同字符串组成的单词列表 words ，其中 words[i] 长度均为 6 。words 中的一个单词将被选作秘密单词 secret 。
另给你一个辅助对象 Master ，你可以调用 Master.guess(word) 来猜单词，其中参数 word 长度为 6 且必须是 words 中的字符串。
Master.guess(word) 将会返回如下结果：
如果 word 不是 words 中的字符串，返回 -1 ，或者
一个整数，表示你所猜测的单词 word 与秘密单词 secret 的准确匹配（值和位置同时匹配）的数目。
每组测试用例都会包含一个参数 allowedGuesses ，其中 allowedGuesses 是你可以调用 Master.guess(word) 的最大次数。
对于每组测试用例，在不超过允许猜测的次数的前提下，你应该调用 Master.guess 来猜出秘密单词。最终，你将会得到以下结果：
如果你调用 Master.guess 的次数大于 allowedGuesses 所限定的次数或者你没有用 Master.guess 猜到秘密单词，则得到 “Either you took too many guesses, or you did not find the secret word.” 。
如果你调用 Master.guess 猜到秘密单词，且调用 Master.guess 的次数小于或等于 allowedGuesses ，则得到 “You guessed the secret word correctly.” 。
生成的测试用例保证你可以利用某种合理的策略（而不是暴力）猜到秘密单词。

示例 1：

输入：secret = “acckzz”, words = [“acckzz”,“ccbazz”,“eiowzz”,“abcczz”], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：
master.guess(“aaaaaa”) 返回 -1 ，因为 “aaaaaa” 不在 words 中。
master.guess(“acckzz”) 返回 6 ，因为 “acckzz” 是秘密单词 secret ，共有 6 个字母匹配。
master.guess(“ccbazz”) 返回 3 ，因为 “ccbazz” 共有 3 个字母匹配。
master.guess(“eiowzz”) 返回 2 ，因为 “eiowzz” 共有 2 个字母匹配。
master.guess(“abcczz”) 返回 4 ，因为 “abcczz” 共有 4 个字母匹配。
一共调用 5 次 master.guess ，其中一个为秘密单词，所以通过测试用例。
示例 2：

输入：secret = “hamada”, words = [“hamada”,“khaled”], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：共有 2 个单词，且其中一个为秘密单词，可以通过测试用例。

提示：
1 <= words.length <= 100
words[i].length == 6
words[i] 仅由小写英文字母组成
words 中所有字符串互不相同
secret 存在于 words 中
10 <= allowedGuesses <= 30

博弈

ctn[i][j] 记录记录和 words[i]有j个字符匹配的字符串数量。
ctn2[i] = $Max_{j:0}^5cnt[i][j]$ 含义是：最坏情况有多少个字符串要排除。
每次选择cnt2[i]最小的字符串。
n = words.length
每次至少排除一个单词，估计最大调用n次。
每次调用的时间复杂度：(6nn) 两两比较字符串的匹配度。
故：总时间复杂度是O(6nnn)。

代码

class Solution {
public:
	void findSecretWord(vector<string>& words, Master& master) {
		const int n = words.size();
		vector<vector<int>> cnt(n, vector<int>(7));
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				const int same = Same(words[i], words[j]);
				cnt[i][same]++;
				cnt[j][same]++;
			}
		}
		map<int, int> mCntIndex;
		for (int i = 0; i < n; i++) {
			int iMax = cnt[i][0];
			for (int j = 1; j <= 5; j++) {
				iMax = max(iMax, cnt[i][j]);
			}
			mCntIndex[iMax] = i;
		}
		const string strGuess = words[mCntIndex.begin()->second];
		const int iSameAns = master.guess(strGuess);
		if (6 == iSameAns) { return; }
		vector<string> newWords;
		for (const auto& s : words) {
			if (iSameAns == Same(s, strGuess)) {
				newWords.emplace_back(s);
			}
		}
		findSecretWord(newWords, master);
	}
	int Same(const string& s1, const string& s2) {
		int same = 0;
		for (int k = 0; k < 6; k++) {
			same += (s1[k] == s2[k]);
		}
		return same;
	}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛