Approach #1: Minimax with Heuristic [Accepted]

Intuition

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.

Algorithm

Store H[i][j] as the number of matches of wordlist[i] and 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.

Complexity Analysis

  • Time Complexity: , where is the number of words, and assuming their length is . Each call to solve is , and the number of calls is bounded by .

  • Space Complexity: .


Analysis written by: @awice.