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.