Word Search II
Explore how to use trie data structures to efficiently search for multiple words in a 2D grid. Learn to handle constraints like sequential horizontal and vertical adjacency of letters, and implement solutions that return all words found. This lesson builds your ability to recognize and solve word search problems using optimal string storage and prefix search techniques common in coding interviews.
We'll cover the following...
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:
- rows, columns
-
words.length -
words[i].length 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
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
From the given list of words, which words are present in the grid?
[EAT, OATH]
[EAT, PEA]
[OATH, PEA]
[PEA]
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.
Try it yourself
Implement your solution in main.go in the following coding playground.
package mainfunc findStrings(grid [][]rune, words []string) []string {// Replace this placeholder return statement with your codereturn make([]string, 0)}