How can I find words in matrix of letters

Question

This is another question I was asked in the telephonic interview:

Given a dictionary and a crossword(2d matrix of characters) find all the dictionary words which can be found in the crossword.

All I could think of was hash the dictionary, find every possible word in the crossword and search the hash. I could not optimize it all.

Must admit Microsoft interview questions are tough :(

Please give me the lines to think on.

Answer 1

How about:

• build a search tree for the dictionary (one level per letter)
• for each position in the grid, start searching through the index, one character at a time, and proceed in each allowed direction until there are no entries left in the index, or you hit a grid boundary

I don't think a hash would be a very useful optimization here.