I recently received this as an interview question. The interview is over and I did not get the job (so I'm not trying to cheat on an interview, just trying to further my knowledge of algorithms and data structures for the future).

The question is as follows:
[font="Times New Roman"]Write a function which will find all the words on ageneralized Boggle™ board. The functionshould take as input the board dimensions, the board, and a dictionary of validwords and it should output the list of all found words to the calling function. You should consider how your approach willperform with a large dictionary and a large board.

My solution to this was to perform a quicksort on the dictionary words. Then I would do a depth first search to get all of the permutations of letters along the board and use a binary search to see if the permutation is in the dictionary.

Based on the interview I guess this is not the best solution and at the time I could not think of a better one. Assuming the O(n log n) quicksort is a pre computational cost, each binary search is O(log n). The only thing I know of that could be faster than O(log n) would be to hash everything and have constant lookup time.

If anyone has some recommendations on better solutions to solving this problem I would love to hear them.

Thanks![/font]

[font="Times New Roman"][/font]

Maybe a trie would be of use here. Build it from the dictionary words, then walk the board tile-by-tile (tagging each as entered), recursively entering the neighbouring tiles and tagging the tile as entered. (do not enter the tile when its tagged). Keep a pointer to the current trie node you are in, and if this tile completes a word, output it. Move on to the next neighbouring tile skipping any tagged tiles(if none are left, return from the recursive function). Move the trie pointer to the new letter if there is one. If not, leave the recursive function. When you exit the recursive function, untag that tile, adjust the trie pointer, and move on to the next. When the top-level recursive function ends, untag the current top-level tile and move on to the next.

Nice answer! I had actually used a trie structure before but didn't think about it until you mentioned it. I think this structure would definitely be more efficient than peforming a binary search each time. Since you would traverse the tree as you form potential words it would be constant time with little overhead for each lookup right?

What is the general lookup time for a structure such as this? Most tree structures are log n, but since this tree isn't balanced it makes things a little different.

Since you will be pointing to the current letter (partial word), I guess it would depend on looking up the sub-nodes. If you use a vector, you will have to iterate to find the next letter. an array of 26 elements would be faster (since you can index the letter) but this could be expensive memory-wise.