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 have a Master
object with a guess(word)
method, which returns the number of exact matches between your guess and the secret word (-1 if the word is not in the input list). You are allowed a maximum number of guesses allowedGuesses
. Write an algorithm to guess the secret word within the allowed number of 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
.
For example:
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
In this case, you should call master.guess("acckzz")
, which returns 6, and the algorithm terminates successfully.
Another Example:
secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
You could call master.guess("hamada")
, which returns 6, or master.guess("khaled")
, which returns 0, and then subsequently call master.guess("hamada")
, which returns 6, and the algorithm terminates successfully.
Constraints:
1 <= words.length <= 100
words[i].length == 6
words[i]
consist of lowercase English letters.wordlist
are unique.secret
exists in words
.10 <= allowedGuesses <= 30
Let's begin with a brute-force approach. The most straightforward way to solve this problem is to iterate through the list of words and guess each word until the Master.guess()
method returns 6 (meaning all characters match). Although simple, this method isn't efficient and doesn't guarantee finding the secret within the allowed number of guesses, especially if the secret word is near the end of the list.
def findSecretWord_brute_force(words, master):
for word in words:
if master.guess(word) == 6:
return
Big O Analysis:
A more efficient approach involves using a minimax strategy combined with random guessing. The main idea is to:
This strategy helps to narrow down the search space more effectively than the brute-force approach.
import random
class Solution:
def findSecretWord(self, wordlist, master):
def matches(w1, w2):
match = 0
for i in range(len(w1)):
if w1[i] == w2[i]:
match += 1
return match
for _ in range(10): # Up to 10 guesses
guess = random.choice(wordlist)
match_count = master.guess(guess)
if match_count == 6:
return
wordlist = [word for word in wordlist if matches(guess, word) == match_count]
Explanation:
matches
function calculates the number of exact matches between two words.wordlist
.wordlist
is filtered to include only words that have the same number of matches with the guess as the secret word would.Big O Analysis:
wordlist
, due to the creation of new lists during filtering.matches
could also provide a slight performance improvement.