Problem description:

This is an interactive problem.

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

1
2
3
4
5
6
7
8
9
Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"], numguesses = 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:

1
2
Input: secret = "hamada", wordlist = ["hamada","khaled"], numguesses = 10
Output: You guessed the secret word correctly.

Constraints:

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

Solution:

Clarify

Does the algorithm I design have to find the secret word within 10 times of guesses?
No, you only need to design an algorithm that can find the secret word in as less times as possible.

The question becomes how to narrow down the candidates after each time we guess?

How to narrow the candidates?

we have x = master.guess(word)

if x == 6, we find the secret word, the algorithm ends

if x != 6, it means secret has exactly x matches with word

We could search in the candidates, and only keep the ones that have exact x matches with word. In this way, we narrow the candidates after we call master.guess(), and guarantee that secret is in candidates left.

How to choose from candidates?

  • option-1: select the first candidate as the input of master.guess() every time
  • option-2: randomly select one word from candidates as the input of master.guess()
  • [Preferred] option-3: calculate matching scores for each candidates, guess with the one with highest score
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
# """
# 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, wordlist: List[str], master: 'Master') -> None:
        def match(w1, w2):
            score = 0
            for i in range(len(w1)):
                if w1[i] == w2[i]:
                    score += 1
            return score
        
        x = 0
        for t in range(10):
            count = [[0 for _ in range(26)] for _ in range(6)]
            # print(count)
            for word in wordlist:
                for i, c in enumerate(word):
                    count[i][ord(c)-ord('a')] += 1
            
            # start from first word
            # try to find a word that has best score to guess
            guess = wordlist[0] 
            best = 0
            for word in wordlist:
                score = 0
                for i, c in enumerate(word):
                    score += count[i][ord(c)-ord('a')]
                
                if score > best:
                    guess = word
                    best = score
            x = master.guess(guess)
            wordlist2 = []
            for word in wordlist:
                if match(word, guess) == x:
                    wordlist2.append(word)
            wordlist = wordlist2

time complexity: $O(n)$
space complexity: $O(n)$
reference:
related problem: