843. 猜猜这个单词
这是一个 交互式问题 。
我们给出了一个由一些 不同的 单词组成的列表 wordlist ，对于每个 wordlist[i] 长度均为 6 ，这个列表中的一个单词将被选作 secret 。
你可以调用 Master.guess(word) 来猜单词。你所猜的单词应当是存在于原列表并且由 6 个小写字母组成的类型 string 。
此函数将会返回一个 integer ，表示你的猜测与秘密单词 secret 的准确匹配（值和位置同时匹配）的数目。此外，如果你的猜测不在给定的单词列表中，它将返回 -1。
对于每个测试用例，你有 10 次机会来猜出这个单词。当所有调用都结束时，如果您对 Master.guess 的调用在 10 次以内，并且至少有一次猜到 secret ，将判定为通过该用例。
示例 1:
输入: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"] 输出: You guessed the secret word correctly. 解释:master.guess("aaaaaa")返回 -1, 因为"aaaaaa"不在 wordlist 中.master.guess("acckzz") 返回6, 因为"acckzz"就是秘密，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", wordlist = ["hamada","khaled"], numguesses = 10 输出: You guessed the secret word correctly.
提示:
1 <= wordlist.length <= 100wordlist[i].length == 6wordlist[i] 只包含小写英文字母wordlist 中所有字符串都 不同secret 在 wordlist 中numguesses == 10原站题解
python3 解法, 执行用时: 100 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-18 15:53:58
# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
# def guess(self, word: str) -> int:
class Solution:
def findSecretWord(self, words: List[str], master: 'Master') -> None:
m = defaultdict(list)
for word1 in words:
for word2 in words:
diff = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
diff += 1
m[word1, diff].append(word2)
s = set(words)
while len(s) > 0:
same = master.guess(list(s)[0])
if same == 6: return
s &= set(m[list(s)[0], 6 - same])
python3 解法, 执行用时: 104 ms, 内存消耗: 16 MB, 提交时间: 2023-09-18 15:51:47
# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
# def guess(self, word: str) -> int:
'''
方法 1：启发式极小化极大算法
显然，可行单词列表中的单词越少越好。如果数据随机，那么我们可以认定这个情况是普遍的。
现在，利用极小化极大算法猜测可行的单词列表。如果我们开始有 N 个单词，我们通过迭代去选择可行单词。
算法
存储 H[i][j] 为 wordlist[i] 和 wordlist[j] 单词匹配数。每次猜测要求之前没有猜过，
按照上面的说法实现极小化极大算法，每次选择猜测的单词是当前可行单词中的一个。
'''
class Solution:
def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
N = len(wordlist)
self.H = [[sum(a==b for a,b in zip(wordlist[i], wordlist[j]))
for j in range(N)] for i in range(N)]
possible, path = range(N), ()
while possible:
guess = self.solve(possible, path)
matches = master.guess(wordlist[guess])
if matches == len(wordlist[0]): return
possible = [j for j in possible if self.H[guess][j] == matches]
path = path + (guess,)
def solve(self, possible, path = ()):
if len(possible) <= 2: return possible[0]
ansgrp, ansguess = possible, None
for guess, row in enumerate(self.H):
if guess not in path:
groups = [[] for _ in range(7)]
for j in possible:
if j != guess:
groups[row[j]].append(j)
maxgroup = max(groups, key = len)
if len(maxgroup) < len(ansgrp):
ansgrp, ansguess = maxgroup, guess
return ansguess