Approach #1: Minimax with Heuristic [Accepted]
We can guess that having less words in the word list is generally better. If the data is random, we can reason this is often the case.
Now let's use the strategy of making the guess that minimizes the maximum possible size of the resulting word list. If we started with words in our word list, we can iterate through all possibilities for what the secret could be.
H[i][j] as the number of matches of
wordlist[j]. For each guess that hasn't been guessed before, do a minimax as described above, taking the guess that gives us the smallest group that might occur.
Time Complexity: , where is the number of words, and assuming their length is . Each call to
solveis , and the number of calls is bounded by .
Space Complexity: .
Analysis written by: @awice.