【博弈】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] = $Ma{x}_{j:0}^{5}cnt[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

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。