Fastest algorithm for finding a word on a word search grid -

Fastest algorithm for finding a word on a word search grid -

i interviewed software developer position. phone interview. asked , has been bugging me day

the interviewer asked me come general approach finding word on word search grid. simplicity, there no need worry memory constraints or searching diagonally on grid (just left right , top bottom).

the best come create hash map on startup of grid programme (before calling word search every time) ... have create hash map of character => row,col indices. way perform initial scan in o(1) time. , there scan left right or top bottom.

i got impression him there improve solution , wasn't there yet. fastest algorithm solving such problem?

if memory isn't issue , can preprocess data, would:

make string representation of grid in row-major order. searching horizontally. make string representation of grid in column-major order, searching vertically.

when given word search for, utilize standard search algorithm (kmp, boyer-moore, etc.) to:

search word in row-major string. reverse word , search in row-major string. search word in column-major string. reverse word , search in column-major string.

that gives balance between simplicity, memory usage, , speed. in fact, it's dead simple because wouldn't need implement search algorithm. utilize whatever provided runtime library.

of course, modify standard search algorithm treat two-dimensional grid one-dimensional string without doing transformation ahead of time. that's more complicated , slower in searching preprocessing, require less memory.

doing in place single scan gets complicated. horizontal searches (i.e. left-to-right , right-to-left) plenty in single scan. , vertical searches in single scan. you'd searching 2 different strings in single pass: word, , reversed version of word.

algorithm