Fastest algorithm for finding a word on a word search grid

Question

I was interviewed for a software developer position. It was a phone interview. Was asked this and it has been bugging me all day

The interviewer asked me to come up with a general approach for finding a word on a word search grid. For simplicity, there is no need to worry about memory constraints or searching diagonally on the grid (just left to right and top to bottom).

The best I could come up with was to create a hash map on startup of the grid program (before calling the word search every time) ... have it create a hash map of character => row,col indices. That way you could perform the initial scan in O(1) time. And then from there basically scan left to right or top to bottom.

I got the impression from him that there was a better solution and that I wasn't there yet. What is the fastest algorithm for solving such a problem?

Answer 1

If memory isn't an issue and I can preprocess the data, then I would:

1. Make a string representation of the grid in row-major order. This is for searching horizontally.
2. Make a string representation of the grid in column-major order, for searching vertically.

When given a word to search for, I would use a standard search algorithm (KMP, Boyer-Moore, etc.) to:

1. Search for the word in the row-major string.
2. Reverse the word and search in the row-major string.
3. Search for the word in the column-major string.
4. Reverse the word and search in the column-major string.

That gives a good balance between simplicity, memory usage, and speed. In fact, it's dead simple because you wouldn't really need to implement the search algorithm. Just use whatever is provided by the runtime library.

Of course, you could easily modify the standard search algorithm to treat the two-dimensional grid as a one-dimensional string without actually doing the transformation ahead of time. That's more complicated and would be slightly slower in searching than preprocessing, but it would require less memory.

Doing it in place with a single scan gets complicated. But you could do the horizontal searches (i.e. left-to-right and right-to-left) easily enough in a single scan. And the vertical searches in a single scan. You'd just be searching for two different strings in a single pass: the word, and a reversed version of the word.