Solution: Word Search II

Statement

You are given a list of strings that you need to find in a 2D grid of letters such that the string can be constructed from letters in sequentially adjacent cells. The cells are considered sequentially adjacent when they are neighbors to each other either horizontally or vertically. The solution should return a list containing the strings from the input list that were found in the grid.

Constraints:

• $1 \leq$ rows, columns $\leq 12$
• $1 \leq$ words.length $\leq 3 \times {10^3}$
• $1 \leq$ words[i].length $\leq 10$
• grid[i][j] is an uppercase English letter.
• words[i] consists of uppercase English letters.
• All the strings are unique.

Note: The order of the strings in the output does not matter.

Solution

By using backtracking, we can explore different paths in the grid to search the string. We can backtrack and explore another path if a character is not a part of the search string. However, backtracking alone is an inefficient way to solve the problem, since several paths have to be explored to search for the input string.

By using the trie data structure, we can reduce this exploration or search space in a way that results in a decrease in the time complexity:

• First, we’ll construct the Trie using all the strings in the list. This will be used to match prefixes.

• Next, we’ll loop over all the cells in the grid and check if any string from the list starts from the letter that matches the letter of the cell.

• Once an letter is matched, we use depth-first-search recursively to explore all four possible neighboring directions.

• If all the letters of the string are found in the grid. This string is stored in the output result array.

• We continue the steps of all our input strings.