Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Word Search II

Explore how to apply the trie data structure alongside backtracking to efficiently find multiple words in a 2D grid. This lesson helps you reduce search space by matching prefixes and using depth-first search, leading to optimized time and space complexity. Understand how to build and traverse tries to tackle complex word search problems.

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:

  • 1≤1 \leq rows, columns ≤12\leq 12
  • 1≤1 \leq words.length ≤3×
...