Guess The Word Solution for Google
Company: Google · Difficulty: Hard · Topics: String, Interactive, Minimax
Problem Statement
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. You will be told the number of matches in your guess.
Given an array of strings wordlist and a master object, return the minimum number of calls to Master.guess to find the secret word.
Examples
Example 1:
Input: wordlist = ["acckzz","ccbazz","eiowzz","abcczz"], secret = "acckzz"
Output: 1
Explanation:
- We guess "acckzz" and get 6 matches, so we found the secret word.
Example 2:
Input: wordlist = ["hamada","khaled"], secret = "hamada"
Output: 1
Explanation:
- We guess "hamada" and get 6 matches, so we found the secret word.
Intuition
The key insight is to use a minimax strategy to minimize the maximum possible number of remaining words after each guess. We want to choose a word that, regardless of the response, leaves us with the smallest possible set of candidate words.
Approach
1. Minimax Strategy: Choose the word that minimizes the maximum size of the remaining candidate set
2. Word Filtering: After each guess, filter the wordlist based on the response
3. Match Counting: Use a helper function to count exact character matches between two words
4. Optimal Guessing: Always choose the word that gives the most balanced split of remaining candidates
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution: Minimax Strategy
Time Complexity: O(n²) - For each guess, we may need to check all remaining words
Space Complexity: O(n) - To store the filtered wordlist