跳至主要內容

843. 猜猜这个单词

843. 猜猜这个单词

🔴   🔖  数组 数学 字符串 博弈 交互  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an array of unique strings words where words[i] is six letters long. One word of words was chosen as a secret word.

You are also given the helper object Master. You may call Master.guess(word) where word is a six-letter-long string, and it must be from words. Master.guess(word) returns:

  • -1 if word is not from words, or
  • an integer representing the number of exact matches (value and position) of your guess to the secret word.

There is a parameter allowedGuesses for each test case where allowedGuesses is the maximum number of times you can call Master.guess(word).

For each test case, you should call Master.guess with the secret word without exceeding the maximum number of allowed guesses. You will get:

  • "Either you took too many guesses, or you did not find the secret word." if you called Master.guess more than allowedGuesses times or if you did not call Master.guess with the secret word, or
  • "You guessed the secret word correctly." if you called Master.guess with the secret word with the number of calls to Master.guess less than or equal to allowedGuesses.

The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).

Example 1:

Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10

Output: You guessed the secret word correctly.

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.

Example 2:

Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10

Output: You guessed the secret word correctly.

Explanation: Since there are two words, you can guess both.

Constraints:

  • 1 <= words.length <= 100
  • words[i].length == 6
  • words[i] consist of lowercase English letters.
  • All the strings of wordlist are unique.
  • secret exists in words.
  • 10 <= allowedGuesses <= 30

题目大意

给你一个由 不同 字符串组成的单词列表 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

解题思路

目标是设计一个算法，通过调用 master.guess() 找到秘密单词。

为了尽量减少调用次数，我们需要在每次调用 master.guess() 后，通过结果缩小候选单词的范围。算法结构如下：

while (words.length) {
	// 从候选列表中选择一个单词
	let guessWord = 'xxxxxx';
	matches = master.guess(guessWord);
	// 更新候选列表，仅保留可能的单词;
  words = words.filter(...)
}

关键问题是：

  • 如何根据 master.guess() 的结果缩小候选列表？
  • 如何选择每次猜测的单词？

1. 缩小候选列表

每次调用 master.guess() 时，会返回当前猜测单词与秘密单词的匹配数 x。通过匹配规则：

  • 若 x == 6，即找到秘密单词，算法结束。
  • 若 x != 6，说明秘密单词与当前猜测单词有 x 个字符相同，其他单词中不符合这一匹配规则的单词可以被排除。

为此，构建一个辅助方法 getMatches 来计算两个单词之间的匹配数。

算法更新为：

while (words.length) {
	// 从候选列表中选择一个单词
	let guessWord = 'xxxxxx';
	matches = master.guess(guessWord);

	// 更新候选列表，仅保留匹配数量一致的单词;
	words = words.filter((word) => getMatches(word, guessWord) == matches);
}

2. 如何选择猜测的单词

每次调用 master.guess() 时，会返回当前猜测单词与秘密单词的匹配数 x，通过概率计算可知：

得到 0 个匹配项的可能性是：(25/26) ^ 6 = 79.03%

也就是说，如果我们盲猜，我们有大约 80% 的机会得到与秘密单词 0 个匹配项。

此时，我们将保留所有 getMatches(word, guessWord) == 0 的候选词，由于所有候选词都是随机生成的，因此我们可以假设有 80% 的候选词会被保留。

由于 master.guess() 接口的调用次数有限，我们希望每次调用接口都可以删除最多的单词，因此我们希望选择一个拥有最多匹配项的候选单词（即与其他单词匹配项为 0 的情况最少）。

选择猜测单词的方法有很多种：

  1. 固定选择：每次都选候选列表中的第一个单词。
  2. 随机选择：每次从候选列表中随机选一个单词。
  3. 根据字母频率选择：统计候选单词中每个字符在各位置的出现频率，选择一个具有最高“匹配分数”的单词进行猜测。

前两种随机的方式并不是每次又有足够的好运，可以在 allowedGuesses 次内猜中秘密单词。

为此，构建一个辅助方法 getBestGuessWord 来得到“匹配分数”最高的单词。

  • 使用一个二维数组 counts 记录每个位置上各字母的出现频率。
  • 遍历候选单词，累加单词中每个字母的出现频率，得到其分数。
  • 选择分数最高的单词作为下一次的猜测单词。

算法更新为：

while (words.length) {
	// 从候选列表中选择一个单词
	let guessWord = getBestGuessWord();
	matches = master.guess(guessWord);

	// 更新候选列表，仅保留匹配数量一致的单词;
	words = words.filter((word) => getMatches(word, guessWord) == matches);
}

复杂度分析

  • 时间复杂度：O(n)
    • 每次调用 getBestGuessWord 的时间复杂度为 O(6 * n) = O(n)，其中 n 是候选单词数量。
    • 过滤后选单词列表的时间复杂度为 O(n)。
    • 在最坏情况下，最多进行 allowedGuesses <= 30 次猜测，因此总时间复杂度为 O(30 * n)，即 O(n)。
  • 空间复杂度：O(n)
    • 需要一个二维数组 counts 来记录每个位置字符的频率，空间复杂度为 O(m * 26) = O(n)。
    • 需要存储候选单词列表，空间复杂度为 O(n)。

代码

/**
 * @param {string[]} words
 * @param {Master} master
 * @return {void}
 */
var findSecretWord = function (words, master) {
	// 计算两个单词的匹配数
	const getMatches = (word1, word2) => {
		let matches = 0;
		for (let i = 0; i < word1.length; i++) {
			if (word1[i] === word2[i]) {
				matches++;
			}
		}
		return matches;
	};

	// 从候选单词中选择一个“重叠分数”最高的单词
	// 目的是选择一个具有代表性，能最大化缩小候选范围的单词
	const getBestGuessWord = () => {
		// 用二维数组记录每个位置上各字母的出现频率
		let counts = new Array(6).fill().map(() => new Array(26).fill(0));
		for (let word of words) {
			for (let i = 0; i < 6; i++) {
				const char = word[i].charCodeAt() - 'a'.charCodeAt(); // 字母的 ASCII 值偏移量
				counts[i][char]++;
			}
		}
		// 遍历候选单词，计算每个单词的重叠分数
		let maxScore = 0,
			guessWord;
		for (let word of words) {
			let score = 0;
			for (let i = 0; i < 6; i++) {
				const char = word[i].charCodeAt() - 'a'.charCodeAt();
				score += counts[i][char]; // 根据每个位置上字母的频率累加分数
			}
			// 更新当前的最优猜测单词
			if (score > maxScore) {
				maxScore = score;
				guessWord = word;
			}
		}
		return guessWord;
	};

	// 主循环，逐步缩小候选单词列表
	while (words.length) {
		const guessWord = getBestGuessWord(); // 选择最优猜测单词
		const matches = master.guess(guessWord); // 调用 master.guess 获取匹配数
		if (matches === 6) return; // 如果匹配数为 6，找到秘密单词，退出
		// 根据匹配数过滤候选单词，仅保留匹配数相等的单词
		words = words.filter((word) => getMatches(word, guessWord) === matches);
	}
};
Copyright © 2024 2xiao