Sirupsen's blog

Letterpress problem
By Sirupsen, 12 years ago, In English

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?

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we use one letter multiple times? Can one letter occur twice in our queries? If answer to the second question is 'no', then we have only 26 different queries and the problems becomes very simple.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you mean 2^26 different queries?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      No, if query is 25 different letters, but it isn't

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, I totally missed that there are exactly 25 letters in the queries.

        → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This is actually an alphabet-size-dimensional range query problem, which is not solvable within plain logarithmic time as far as I know. But one can possibly exploit the fact that "coordinates" of words in dictionary are very low positive integers.

→ Reply