Solution: Word Search

Statement

Given an m x n grid of characters, board, and a string word, return TRUE if word exists in the grid.

The word can be formed by connecting letters of sequentially adjacent cells. The cells are considered sequentially adjacent when neighbors are either horizontally or vertically neighbors. Each cell can be used only once while forming the word.

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 and uppercase English letters.

Solution

We must traverse all the grid elements to search for a word in a 2-D grid. The sequence of letters that combine to make a word can be found starting from any index in the grid. Therefore, we must 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. This will help us traverse all the possibilities to find the specific word without using the extra space needed to keep track of the cells’ visited or unvisited status.