Guess the Word
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:
-1ifwordis not fromwords, 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 calledMaster.guessmore thanallowedGuessestimes or if you did not callMaster.guesswith the secret word, or"You guessed the secret word correctly."if you calledMaster.guesswith the secret word with the number of calls toMaster.guessless than or equal toallowedGuesses.
The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).
Example 1:
Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation:
Example 2:
Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation: Since there are two words, you can guess both.
Constraints:
1 <= words.length <= 100words[i].length == 6words[i]consist of lowercase English letters.- All the strings of
wordlistare unique. secretexists inwords.10 <= allowedGuesses <= 30
Solve it on LeetCode
Approaches
1. Random Guess
Intuition:
The simplest solution involves randomly guessing words from the word list. This approach lacks strategic guessing but doesn't require complicated logic. The only check is to ensure you don't guess the same word twice.
Steps:
- Randomly select a word from the list of available words.
- Call the
guessfunction with the selected random word. - Continue guessing until the correct word is guessed (i.e.,
guessreturns the word length).
Code:
- Time Complexity: O(N), where N is the number of attempts (in this method, 10 maximum).
- Space Complexity: O(1), as no additional data structures are needed.
2. Minimax Strategy
Intuition:
A more informed approach is to use minimax to reduce the candidate pool aggressively by minimizing the maximum number of words that could remain after a guess. This strategy leads to fewer guesses by attempting to maximize information gain.
Steps:
- Count matches for each possible word against all others.
- Choose a word that, on average, splits the possibility space well.
- Use guessed similarity (number of letter matches) to filter the list.
- Repeat until the correct word is guessed.
Code:
- Time Complexity: O(N^2 * L), where N is the number of words and L is the length of each word.
- Space Complexity: O(N), maintaining a filtered list of candidate words.
3. Optimal Data Filtering
Intuition:
Incorporating chosen strategic guessing along with data filtering reduces unnecessary guesses significantly. The idea is to reduce candidate words as much as possible each turn.
Steps:
- For each guess, calculate the number of matching letters for every pair of words.
- Optimize the next guess based on its ability to partition the wordpool efficiently.
- Break the loop when guessed successfully.
Code:
- Time Complexity: O(N^2 * L), due to double iteration over the word list.
- Space Complexity: O(N), due to copied lists of candidate words.