Grid Search

Problem statement

Given a grid of characters and a list of strings words, return all the words present in the grid. While searching the grid, you can move to adjacent cells in four directions: up, down, left, and right. The same cell cannot be used more than once in the same word.

Example 1

Sample input

Sample output

Explanation

"cat" is present in the grid at coordinates [0,0] --> [0,1] --> [1,1]
"hat" is present in the grid at coordinates [2,0] --> [3,0] --> [4,0]

Example 2

Sample input

Sample output

Explanation

"cap" is present in the grid at coordinates [2,2] --> [2,3] -->[3,3]
"boat" is present in the grid at coordinates [0,0] --> [0,1] --> [1,1] --> [2,1]

Try it yourself

Try to solve the problem yourself before reading the solution.

Intuition

Let's simplify the problem. Assume we're given a grid and are supposed to find a single string in it. The most intuitive solution to this problem is to iterate the grid cells one by one until the first letter of the word matches the cell, and then from that cell, recursively walk along its neighbors in the four potential directions to find the rest of the word.

The given problem is an extension of this problem. Instead of a single word, we search for multiple words. Here also, we can start from every cell and build a word by backtracking using depth-first search (DFS) to explore and exhaust every possible path. Once we've traveled a path that makes a valid string present in the list, we can add it to our answer and keep moving forward.

We need to do some pruning and stop searching when the current character is not in any word. But how do we instantly know the current character is invalid? Or, how do we instantly know if the prefix we've formed in the recursive call so far is valid? Will it ever form a valid word?

If we know that there does not exist any match of a word in the dictionary for a given prefix, then we wouldn't need to explore further in a certain direction. And this would greatly reduce the exploration space and improve the backtracking algorithm's performance. Since we're dealing with prefixes here, we'll use tries to solve this: we'll add all the words in the tries and use them to identify whether a prefix string is valid.

Algorithm

Below is the summary of the algorithm.

Step 1: Insert input words in a trie

Construct a trie with the words given in the input list.

Step 2: Explore recursively

Iterate over all the cells of the grid and call a recursive function starting from the cell to find the word. From each cell, start the backtracking exploration and check if there exists any word in the dictionary that starts with the letter in the cell.

During the recursive function call, explore the neighbor cells (up, down, left, and right) around the current cell for the next recursive call. At each call, check if the sequence of letters that we've traversed so far matches any word in the dictionary by using the isEndOfWord flag in the trie.

During the recursive call, if the character of the current cell doesn't have a valid path in the trie prefix so far, stop the recursive call and backtrack.

One important point to note here is we can't use the same cell more than once in a single word. To achieve this we can use a boolean value for visited array for each recursive call so we don't call the same cell again in our DFS calls for the current word.

Visualization

The pictures below represents the word searching procedure.

Complexity analysis

Variables

• Number of cells in the grid = ...