Solution: Word Search

Statement#

Given an $m \times n$ 2D grid of characters and word as a string, we need to determine if the word can be constructed from letters of sequentially adjacent cells. The cells are considered sequentially adjacent when they are neighbors to each other either horizontally or vertically. The function should return TRUE if the word can be constructed and FALSE otherwise.

Constraints:

• m $=$ board.length
• n $=$ board[i].length, where $0 \leq$ i $<$ m
• $1 \leq$ m, n $\leq 6$
• $1 \leq$ word.length $\leq 15$
• board and word consist of only lowercase or uppercase English letters.
• The search is not case-sensitive.

Pattern: Backtracking#

In order to search for a word in a 2-D grid, we need to traverse all the elements of the grid. The sequence of letters that combine to make a word can be found starting from any index in the grid. Therefore, we need to find that word in all possible directions, starting from a particular index. However, what would we do if we learned that the current path would not lead to the solution?

The answer to the problem above lies in backtracking. We can move backward from the current index and resume the search for the required word along one of the other possible paths.

Solution#

This problem can be solved efficiently by implementing the backtracking technique. This will help us traverse all the possibilities to find the specific word without using the extra space needed to keep track of the visited or non-visited status of the cells.

Note: In the following section, we’ll gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

For each cell on the 2D grid, we have four paths we can take next. If the chosen path is incorrect, we’ll backtrack and choose a different path until the word is found or all possibilities are exhausted. We can implement the DFS algorithm using a recursive function.

Note: Although the DFS algorithm is classically implemented on a tree or graph data structure, it may also be applied wherever the concept of connectedness is found in a data structure. In the 2D array provided as input, we see that each character located at cell {$i, j$} is connected to its four potential neighbors, each addressable as cells {$i+1, j$} (the character below), {$i-1, j$} (the character above), {$i, j+1$} (the character to the right), and {$i, j-1$} (the character to the left). In graph terminology, we can say that each cell in the input grid has a minimum of two and a maximum of four edges.

We’ll apply a depth-first search for each cell of the grid. We’ll check for the base case in the depth_first_search function. The base case occurs when we have matched all characters in the word individually, indicating that we have found the whole word in the grid. If this is the case, we have no more letters to explore in the word, so the length of the word becomes $0$. Therefore, we return TRUE.

After the base case, we need to check if the current cell is a valid candidate for the next character of the word. In line 20, we do this by checking if the row and column indices are within the bounds of the grid. In line 21, we check if the character in the cell matches the next character in the word. If any of these conditions are not satisfied, we cannot proceed with the current cell, and we return FALSE to backtrack and explore other paths.

After ensuring that the current cell is not out of bounds and contains the next character of the word, we mark the cell as visited by setting it to $*$. Then, we iterate over the four possible choices (up, down, right, left) and call the depth_first_search function recursively with the updated row and column indices and the remaining portion of the word.

For each possible choice, we check if the recursive call to depth_first_search returns TRUE. If the call returns TRUE, indicating that we have found the whole word, we return TRUE. If not, we will continue the loop and try the next possible choice. If none of the choices lead to finding the whole word, we will return FALSE.

When the function has finished exploring all possible paths from the current cell and returns FALSE, we’ll revert the cell’s original value to unmark it and allow it to be visited in other paths. This is important because, if we don’t reset the cell’s value, it would still be marked as visited, and the search would be incomplete or miss out on other possible paths.