I was playing the Letterpress iPhone App the other day, and I thought about how people would cheat in this game. (You do not ned to know the mechanics of Letterpress to understand this problem.)

Basically you want to form long words given 25 letters. A naive approach to obtain a long word you can form in the game, would be to go through a list of words, then check each word if it can be made from those 25 letters. This is O(N * 25).

However, I thought of a slightly more complex version of the problem, which I was not able to solve:

What if you are given Q queries of 25 letters, and you want to know which words can be formed from those letters, without traversing the word list for each query? Is it possible to run each query in O(log(n)) time, if the word list is stored in some clever data structure?