猜猜这个单词

标签: 数组数学字符串博弈交互

难度: Hard

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

Submission

运行时间: 28 ms

内存: 0.0 MB

# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Master:
#    def guess(self, word):
#        """
#        :type word: str
#        :rtype int
#        """

class Solution:
    def findSecretWord(self, wordlist, master):
        """
        :type wordlist: List[Str]
        :type master: Master
        :rtype: None
        """
        def match(str1,str2):
            count = 0
            for ch1,ch2 in zip(str1,str2):
                if ch1==ch2:
                    count+=1
            return count
            
        
        n=0
        while n<6:
            w = random.choice(wordlist)
            n = master.guess(w)
            # update w_list
            w_list = []
            for word in wordlist:
                if match(w,word)==n:
                    w_list.append(word)
            wordlist = w_list.copy()

Explain

该题解采用随机猜测和缩减候选词列表的方法来猜出秘密单词。具体思路为：随机选择一个单词进行猜测，根据返回的匹配字母数，将与当前猜测单词有相同匹配字母数的单词保留，其余的单词从候选列表中删除。重复这个过程，直到猜中秘密单词或达到允许的最大猜测次数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findSecretWord(self, wordlist, master):
        """
        :type wordlist: List[Str]
        :type master: Master
        :rtype: None
        """
        def match(str1, str2):
            # 计算两个字符串的匹配字母数
            count = 0
            for ch1, ch2 in zip(str1, str2):
                if ch1 == ch2:
                    count += 1
            return count
        
        n = 0
        while n < 6:
            # 随机选择一个单词进行猜测
            w = random.choice(wordlist)
            n = master.guess(w)
            
            # 更新单词列表，保留与当前猜测单词有相同匹配字母数的单词
            w_list = []
            for word in wordlist:
                if match(w, word) == n:
                    w_list.append(word)
            wordlist = w_list.copy()

Explore

这样做的目的是缩小可能的候选词列表，以更快地找到秘密单词。如果一个单词与你的猜测单词有相同的匹配字母数，这意味着它可能是秘密单词。反之，如果匹配字母数不同，可以确定这些单词不可能是秘密单词，因此将它们从候选列表中删除可以提高猜测的效率。

这个结论基于一个优化的猜测策略和某些特定的问题设定，比如单词列表的大小和单词的特性。在实际使用中，如果随机选择单词的策略不够优化，或者单词列表特别大，可能会需要更多的猜测次数。因此，这个结论并不是绝对的，实际所需的猜测次数可能因具体情况而异。

在这个特定的场景下，我们假设所有单词的长度是相同的，因为它们通常来自于一个固定格式的词汇表。因此，使用`zip`函数来比较两个字符串是合适的，因为它会在达到任一字符串的末尾时停止。如果在不同场景中字符串长度可能不同，那么比较之前需要添加额外的长度检查逻辑。

在提供的解决方案中，每次猜测后都会更新候选单词列表，只保留那些与当前猜测单词具有相同匹配字母数的单词。这意味着已经猜测过且不符合匹配要求的单词会被自动排除。因此，在每次迭代中选择单词时，我们实际上是从未被排除的、仍然可能是秘密单词的候选列表中随机选择，从而避免了重复猜测相同的单词。