Problem

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).

https://leetcode.com/problems/guess-the-word/

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

Test Cases

1
2
3
4
5
6
7
8
9
# """
# 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:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import pytest

from solution import Solution
from solution2 import Solution as Solution2


class Master:
    def __init__(self, secret: str, words: list[str], allowedGuesses: int):
        self._secret = secret
        self._words = words
        self._chance = allowedGuesses
        self._win = False

    @property
    def win(self) -> bool:
        return self._win

    def guess(self, word: str) -> int:
        assert self._chance > 0
        self._chance -= 1
        if word not in self._words: return -1
        correct = sum(1 for a, b in zip(self._secret, word) if a == b)
        if correct == len(self._secret):
            self._win = True

        return correct


@pytest.mark.parametrize('secret, words, allowedGuesses, expected', [
    ("acckzz", ["acckzz","ccbazz","eiowzz","abcczz"], 10, True),
    ("hamada", ["hamada","khaled"], 10, True),

    (
        "hbaczn",
        ["gaxckt","trlccr","jxwhkz","ycbfps","peayuf","yiejjw","ldzccp","nqsjoa","qrjasy","pcldos","acrtag","buyeia","ubmtpj","drtclz","zqderp","snywek","caoztp","ibpghw","evtkhl","bhpfla","ymqhxk","qkvipb","tvmued","rvbass","axeasm","qolsjg","roswcb","vdjgxx","bugbyv","zipjpc","tamszl","osdifo","dvxlxm","iwmyfb","wmnwhe","hslnop","nkrfwn","puvgve","rqsqpq","jwoswl","tittgf","evqsqe","aishiv","pmwovj","sorbte","hbaczn","coifed","hrctvp","vkytbw","dizcxz","arabol","uywurk","ppywdo","resfls","tmoliy","etriev","oanvlx","wcsnzy","loufkw","onnwcy","novblw","mtxgwe","rgrdbt","ckolob","kxnflb","phonmg","egcdab","cykndr","lkzobv","ifwmwp","jqmbib","mypnvf","lnrgnj","clijwa","kiioqr","syzebr","rqsmhg","sczjmz","hsdjfp","mjcgvm","ajotcx","olgnfv","mjyjxj","wzgbmg","lpcnbj","yjjlwn","blrogv","bdplzs","oxblph","twejel","rupapy","euwrrz","apiqzu","ydcroj","ldvzgq","zailgu","xgqpsr","wxdyho","alrplq","brklfk"],
        10,
        True
    ),
    (
        "ccoyyo",
        ["wichbx","oahwep","tpulot","eqznzs","vvmplb","eywinm","dqefpt","kmjmxr","ihkovg","trbzyb","xqulhc","bcsbfw","rwzslk","abpjhw","mpubps","viyzbc","kodlta","ckfzjh","phuepp","rokoro","nxcwmo","awvqlr","uooeon","hhfuzz","sajxgr","oxgaix","fnugyu","lkxwru","mhtrvb","xxonmg","tqxlbr","euxtzg","tjwvad","uslult","rtjosi","hsygda","vyuica","mbnagm","uinqur","pikenp","szgupv","qpxmsw","vunxdn","jahhfn","kmbeok","biywow","yvgwho","hwzodo","loffxk","xavzqd","vwzpfe","uairjw","itufkt","kaklud","jjinfa","kqbttl","zocgux","ucwjig","meesxb","uysfyc","kdfvtw","vizxrv","rpbdjh","wynohw","lhqxvx","kaadty","dxxwut","vjtskm","yrdswc","byzjxm","jeomdc","saevda","himevi","ydltnu","wrrpoc","khuopg","ooxarg","vcvfry","thaawc","bssybb","ccoyyo","ajcwbj","arwfnl","nafmtm","xoaumd","vbejda","kaefne","swcrkh","reeyhj","vmcwaf","chxitv","qkwjna","vklpkp","xfnayl","ktgmfn","xrmzzm","fgtuki","zcffuv","srxuus","pydgmq"],
        10,
        True
    ),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, secret, words, allowedGuesses, expected):
    master = Master(secret, words, allowedGuesses)
    sol.findSecretWord(words, master)
    assert master.win == expected

Thoughts

设拿一个单词 word 调用 Master.guess 返回结果为 m。显然如果 m = 6 就猜对了，可以停止。否则有 0 ≤ m ≤ 5。

因为 secret 跟 word 的匹配度（the number of exact matches）为 m，那么 words 中所有跟 word 匹配度不为 m 的单词，一定不可能是 secret，可以排除掉。想要猜的最快，就要尽可能多地排除掉候选单词。

事先计算任意两个单词之间的匹配度。对于某个单词，看每个匹配度能匹配到的单词数量，取最大值，即为猜测这个单词之后，剩余候选单词数量的上限。对所有的候选单词，取剩余候选单词数量上限最小的那个进行猜测。

时间复杂度为 O(k * n²)，空间复杂度 O(n²)，其中 k 是猜测次数，根据题目限制可以认为是常数。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
#     def guess(self, word: str) -> int:


from collections import Counter
from math import inf


class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        n = len(words)
        matches = [[6] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                m = sum(1 for a, b in zip(words[i], words[j]) if a == b)
                matches[i][j] = matches[j][i] = m

        candidates = list(range(n))
        while True:
            choice, remain = 0, inf
            for i in candidates:
                counter = Counter(matches[i][j] for j in candidates)
                m, cnt = counter.most_common(1)[0]
                if cnt < remain:
                    choice, remain = i, cnt

            m = master.guess(words[choice])
            if m == 6:
                break

            candidates = [i for i in candidates if matches[choice][i] == m]

Faster but May Fail

因为上边虽然每次都选剩余候选单词数量上限最小的单词，但根据猜测结果筛选之后，实际剩余的候选单词数量可能会多很多，那不如直接随机选择。

每次随机挑一个候选单词去猜测，然后删掉匹配度不一致的其他候选词。时间复杂度是 O(k * n)，空间复杂度 O(n)。但是猜测的数量就不太稳定，有时候提交后测试会失败（猜测数量达到上限）。

solution2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
#     def guess(self, word: str) -> int:


import random


class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        match = lambda i, j: sum(1 for a, b in zip(words[i], words[j]) if a == b)
        n = len(words)
        candidates = list(range(n))

        while True:
            choice = random.choice(candidates)
            m = master.guess(words[choice])
            if m == 6: break

            candidates = [i for i in candidates if match(choice, i) == m]
hard
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~