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≤1 \leq rows, columns ≤12\leq 12
  • 1≤1 \leq words.length ≤3×103\leq 3 \times {10^3}
  • 1≤1 \leq words[i].length ≤10\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.

Examples#

Created with Fabric.js 3.6.6 Words to search: [REINDEER, IN, RAIN] C O L I M I N L M O A L I E O R T A S N S I T A C

1 of 5

Created with Fabric.js 3.6.6 Words to search: [REINDEER, IN, RAIN] C O L I M I N L M O A L I E O R T A S N S I T A C Words found: [IN]

2 of 5

Created with Fabric.js 3.6.6 Words found: [IN, RAIN] Words to search: [REINDEER, IN, RAIN] C O L I M I N L M O A L I E O R T A S N S I T A C

3 of 5

Created with Fabric.js 3.6.6 P S L A M O P U R O O L I E O R T A S N S I T A C Words to search: [DESTINATIONS, POPULAR]

4 of 5

Created with Fabric.js 3.6.6 Words found: [POPULAR] P S L A M O P U R O O L I E O R T A S N S I T A C Words to search: [DESTINATIONS, POPULAR]

5 of 5

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Word Search II

1

From the given list of words, which words are present in the grid?

OAACETAEIHKSIZLD\begin{matrix} O & A & A & C\\ E & T & A & E\\ I & H & K & S\\ I & Z & L & D \end{matrix}

[OATH,PEA,EAT][OATH, PEA, EAT]

A)

[EAT, OATH]

B)

[EAT, PEA]

C)

[OATH, PEA]

D)

[PEA]

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Insert all the input strings in the trie.

Search through the grid cells, looking in all four possible adjacent directions to see if there is a string in the input strings that starts with a letter in the cell.

Using trie, for each cell in the grid, check if the traversed sequence of letters matches any string in the input strings.

If the sequence matches a string in the input strings, include it in the result list.

Return the result list.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided useful code templates in the other files that you may build on to solve this problem.

Python
main.py
trie.py
trie_node.py
Input #1
Input #2
Word Search II

Solution: Design Add and Search Words Data Structure

Solution: Word Search II