We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Guess the Word

Difficulty: Hard

Problem Description

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

Key Insights

  • The secret word is guaranteed to be in the list of words.
  • Each guess can provide feedback in the form of exact matches, which can be used to narrow down possibilities.
  • A systematic approach to guessing can minimize the number of calls to Master.guess.

Space and Time Complexity

Time Complexity: O(n^2) - where n is the size of the words array, since we may need to compare each word with each other to deduce the correct one. Space Complexity: O(n) - for storing the list of valid words during the guessing process.

Solution

To solve this problem, we can use a combination of filtering and feedback analysis. The approach involves:

  1. Making an initial guess from the list of words.
  2. Using the feedback from Master.guess to narrow down the possible candidates for the secret word based on the exact matches.
  3. Repeating the process until the secret word is found or the maximum number of allowed guesses is reached.

We can utilize a list to track the remaining valid words and continuously refine this list based on the feedback from our guesses.

Code Solutions

class Solution:
    def findSecretWord(self, words, master):
        # Start with the list of all words
        remaining_words = words[:]
        
        for _ in range(10):  # We have at most 10 guesses
            # Choose a candidate word (could be any word from remaining)
            guess_word = remaining_words[0]
            # Make a guess
            matches = master.guess(guess_word)
            
            if matches == 6:
                return  # Found the secret word
            
            # Refine remaining words based on the number of matches
            remaining_words = [word for word in remaining_words if self.matchCount(word, guess_word) == matches]

    def matchCount(self, word1, word2):
        # Count the number of exact matches between two words
        return sum(a == b for a, b in zip(word1, word2))
← Back to All Questions