title: Fastest algorithm for finding a word on a word search grid
body: <p>I was interviewed for a software developer position. It was a phone interview. Was asked this and it has been bugging me all day</p>
  
  <p>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).</p>
  
  <p>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 <strong>character</strong> => <strong>row,col indices</strong>. 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.</p>
  
  <p>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?</p>