Word Search Apple Python Interview Question

Given an grid of characters and a string , return if exists in the grid.

For the word to exist, you must be able to construct it from a sequence of cells, where each is adjacent (horizontally or vertically, but not diagonal) to the next one in the sequence. The same cell may not be used twice.

Example #1

Input: board = [['A', 'L', 'E', 'D'], ['E', 'F', 'M', 'H'], ['I', 'R', 'U', 'L']] , word = "LEMUR"

Output: True

Example #2

Input: board = [['A', 'B', 'C', 'D'], ['P', 'E', 'T', 'H'], ['I', 'R', 'K', 'L']] , word = "PETER"

Output: False

Explanation: Cannot reuse the "E".

Example #3

Input: board = [['F', 'B', 'C', 'D'], ['E', 'M', 'G', 'H'], ['I', 'J', 'U', 'R']] , word = "FEMUR"

Output: False

Explanation: Cannot go diagonally from "M" to "U".

Intuition

For most problems, you'll gain intuition by trying to solve an example case yourself, as a human would do it. Seriously, go through the grid and search for DataLemur in a systematic way, dragging your finger across the grid.

Talk out loud – explain clearly what process your brain/finger are following. Being so explicit about your thought process is exactly how you train your brain to effortlessly convert an algorithms into code.

Here's the process we are using:

For each starting location...

1. Check if the letter at this location matches the first letter of the word
2. If so, check if any neighbors match the next letter in the word
3. Keep going until you reach the end of the word

In step 2 we are asking the same question over and over again, but each time we have less and less of the word left to check. That aspect makes this problem a great candidate for a recursive solution.

For the recursive check, we'll need to know both where we are on the board and in the word. Let's call the function that will do this:

At the top-most level, we'll kick off to look for the word starting from each cell on the grid.

Recursion

The function will answer the question: Is it possible to find from location on the board? As this is a recursive function, we'll need a base case, and a recursive case.

Base Case

This is how we'll know we are done. We already wrote that down in step 3 -- we are done once we reach the end of the word.

Recursive Case

If we are not yet at the end of the word, we check that the current letter matches and then make sure that the rest of the search is successful from at least one of its neighbors.

The last (and tricky!) piece is making sure that we don't use the same tile twice. A simple way to do this is to overwrite the position to indicate that it is in use for the current search, and then restoring it if it turns out to be a dead end.

This makes it so that the position won't ever be able to match another letter in the word so long as it is in use. Try to really understand why this works!

Code