The problem statement asks us to win the game against our server. A game position is completely determined by the current string S. For each string we can say if it is winning (i.e. player to move can win the game) or losing (i.e. player to move will lose the game if his opponent plays optimally).
Standard reasoning from the combinatorial game theory can be applied:
We say that the position represented by a string S is winning if there is a letter α such that string Sα is a valid string (not in the wordlist, but a prefix of some word in the wordlist) and the position Sα is losing. It means that the current player can force his opponent into a losing position.
We say that a position S is losing if for each letter α the string Sα is either an invalid string (it is in the wordlist or it is not a prefix of any word in the wordlist), or the position Sα is winning. It means that the current player is forced to immediately lose the game or to create a winning position for his opponent.
This recursive definition is valid because the game is finite – its length is bounded by the longest word in the wordlist.
We are only interested in positions that correspond to prefixes of words in the wordlist. A conceptually nice way how to compute which of them are winning is to insert all the words in the wordlist into a trie. The vertices of the trie then correspond to all the positions in the game that interest us. We can compute which ones are winning for example using a DFS traversal of the trie. (This directly corresponds to simply applying the recursive definition mentioned above.)
To solve the hard test case we have to play in such a way that minimizes the length of gameplay (otherwise you will hit he submission limit). To do this, we can extend the above definition. For each position we will compute the number of moves remaining, given that the winning player tries to minimize, and the losing player tries to maximize it.
Implementation of this idea leads to an algorithm which uses time proportional to size of the wordlist for precomputation, and constant time to determine the optimal move for a given position. A simpler implementation without the trie, representing each position simply by its string, was sufficient.