Skip to main content

212. Word Search II

hard

Given a 2D grid and a list of words, return every word that can be traced on the grid. The dramatic upgrade from Word Search where a Trie is the only way to keep grading from timing out.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Examples

Example 1

Input
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output
["eat","oath"]

Example 2

Input
board = [["a","b"],["c","d"]], words = ["abcb"]
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Repeating Word Search for each word is too slow when words.length is large.

Hint 2

Build a Trie of all words. DFS the grid once carrying a Trie node alongside the cell.

Hint 3

At each step, advance to trieNode.children[currentLetter]. If it's a leaf with a word, add to result and mark word found.

Hint 4

Prune the Trie as words are found — delete the leaf and recurse up removing empty children to shrink the search.

Solution approach

Reveal approach

Build a Trie from words: each node has children indexed by letter and an optional 'word' attribute set on terminal nodes. DFS the grid: dfs(r, c, node): let ch = board[r][c]; child = node.children[ch]; if no child, return. If child.word is set, push child.word to result and clear it (dedups + signals 'found'). Mark board[r][c] = '#', recurse into 4 neighbors with child, restore. Optionally prune: if child has no children left after recursing, delete it from node — this gradually shrinks the Trie and cuts huge amounts of search. Time is O(m * n * 4^L) where L = max word length; pruning makes the constant much better in practice.

Complexity

Time
O(m * n * 4^L)
Space
O(total chars across words)

Related patterns

  • trie
  • backtracking
  • dfs

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta

Practice these live with InterviewChamp.AI

Drill Word Search II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →