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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Guess the Word

Number: 873

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Bloomberg, Apple, Meta, Verkada, Dropbox

Problem Description

Given an array of unique six-letter words and a hidden secret word (which is one of the words), you have access to a helper interface Master.guess(word) that returns the number of characters in the guessed word that exactly match the secret word in both position and value. You must determine the secret word by calling Master.guess within a limited number of allowed guesses. The challenge lies in selecting guesses in a way that minimizes the search space, while always ensuring the secret word can eventually be deduced.

Key Insights

  • Use a strategy based on eliminating words from the candidate set based on the number of matching letters returned by the Master.guess call.
  • Define a helper function to calculate the number of matching character positions between any two words.
  • Each guess helps you narrow down the candidate words: you only keep words in the list that would give the same matching count with the guessed word as the Master.guess output.
  • Although brute-force could work given a small wordlist, a strategy such as minimax or simply narrowing down the candidate set by eliminating non-conforming words is sufficient.
  • This problem is interactive in nature; careful management of the guess count and candidate filtering is paramount.

Space and Time Complexity

Time Complexity: In the worst-case scenario, each guess requires checking against all candidates with O(n) comparisons and each comparison takes O(word_length), leading to O(n^2 * word_length). Space Complexity: O(n) for storing the candidate list.

Solution

The solution involves iteratively guessing a word from the current candidate list and then filtering the candidate list based on the number of matching letters reported by Master.guess. A helper function computes the number of matching letters between two words. After each guess, the candidate list is reduced to only those words that would have produced the same matching score with the guessed word. This process continues until the secret word is found or the allowed number of guesses is exceeded. The use of candidate elimination is a key trick here, ensuring that each guess reduces the possible search space.

Code Solutions

# Python solution for "Guess the Word" problem

class Solution:
    def findSecretWord(self, wordlist, master):
        # Helper function to count matching positions between two words
        def countMatches(word1, word2):
            matches = 0
            for c1, c2 in zip(word1, word2):
                if c1 == c2:
                    matches += 1
            return matches
        
        # Initially, all words are candidates
        candidates = wordlist[:]
        
        # Iterate until we find the secret word or run out of allowed guesses
        for _ in range(10):  # allowed guesses is at most 10-30, using 10 as a safe upper bound
            # pick a candidate word - a simple strategy is to select the first word
            guess_word = candidates[0]
            
            # Make a guess using Master.guess; it returns the count of matching characters
            matchCount = master.guess(guess_word)
            
            # If the secret word is found (6 matches for a 6-letter word), return immediately
            if matchCount == 6:
                return
            
            # Otherwise filter the candidates based on the match count
            new_candidates = []
            for word in candidates:
                if countMatches(guess_word, word) == matchCount:
                    new_candidates.append(word)
            candidates = new_candidates
← Back to All Questions