How do you solve Word Search II?

Build a Trie from the list of words. For each cell in the board, start a DFS that explores neighbors only if the current path matches a prefix in the Trie. Mark visited cells to avoid reuse. When a Trie node indicates a complete word, add it to the result set. This approach ensures each path is explored only once per prefix, achieving efficient pruning and correctness.

What pattern does Word Search II use?

The Pattern: Trie (Prefix Tree) combined with Backtracking (DFS) for Efficient Multi-Word Search The Heuristic: Use a Trie to represent all words so that during DFS, paths that do not match any prefix can be abandoned immediately, preventing redundant exploration and enabling efficient simultaneous search for multiple words.

Word Search II — Trie

Q: What is the time complexity of Word Search II?

O(M * 4 * 3^(L-1)). M is the number of cells in the board. Each DFS explores up to 4 neighbors, but after the first step, at most 3 neighbors are explored to avoid revisiting the previous cell. L is the maximum length of words. Trie pruning reduces unnecessary paths, making the search efficient.

Problem

Given a 2D board of characters and a list of words, return all words from the list that can be formed by sequentially adjacent letters on the board, where adjacent letters are horizontally or vertically neighboring and each letter cell may not be used more than once per word.

1 ≤ board.length ≤ 12
1 ≤ board[i].length ≤ 12
1 ≤ words.length ≤ 3 * 10⁴
1 ≤ words[i].length ≤ 10
board and words[i] consist of lowercase English letters

Example

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"]

The algorithm first builds a Trie from the list of words to enable efficient prefix checks. Starting from each cell, it performs DFS to explore all possible paths. For example, starting at board[0][0] = 'o', it explores neighbors to form 'oath', which is found in the Trie and added to the result. Paths that do not match any prefix in the Trie are pruned early, avoiding unnecessary exploration. The critical moment is pruning paths that do not lead to any word, which drastically reduces the search space compared to naive backtracking.

Approach

Straightforward Solution

A naive approach tries to find each word independently by DFS on the board, resulting in O(m * n * 4^l) per word (m,n board dimensions, l word length), which is too slow for large word lists.

Core Observation

The problem requires searching for multiple words on a grid with adjacency constraints. A brute-force approach checking each word independently is inefficient because it repeats similar searches. The key is to share prefix information among words to prune searches early.

Path to Optimal

Preview

The key recognition signals are 'multiple words', 'prefix matching', and 'adjacent letters'. These indicate using a Trie to represent all words simultaneously, enabling prefix pruning during DFS…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build a Trie from the list of words. For each cell in the board, start a DFS that explores neighbors only if the current path matches a prefix in the Trie…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(M * 4 * 3^(L-1))

M is the number of cells in the board. Each DFS explores up to 4 neighbors, but after the first step, at most 3 neighbors are explored to avoid revisiting the previous cell. L is the maximum length of words. Trie pruning reduces unnecessary paths, making the search efficient.

Space

O(N * L)

N is the number of words and L is the average length. The Trie requires O(N * L) space to store all words. The recursion stack uses O(L) space. The visited set uses O(M) space but is bounded by board size.

Solution

Python

1class TrieNode:
  def __init__(self):
      self.children = {}
      self.is_word = False
5
  def add_word(self, word):
      curr = self
      for c in word:
          if c not in curr.children:
              curr.children[c] = TrieNode()
          curr = curr.children[c]
      curr.is_word = True
13
14class Solution:
  def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
      root = TrieNode()
      for w in words:
          root.add_word(w)
19
      ROWS, COLS = len(board), len(board[0])
      res, visit = set(), set()
22
      def dfs(r, c, node, word):
          if (r < 0 or c < 0 or
              r == ROWS or c == COLS or
              (r, c) in visit or board[r][c] not in node.children):
              return
28
          visit.add((r, c))
          node = node.children[board[r][c]]
          word += board[r][c]
          if node.is_word:
              res.add(word)
34
          dfs(r + 1, c, node, word)
          dfs(r - 1, c, node, word)
          dfs(r, c + 1, node, word)
          dfs(r, c - 1, node, word)
          visit.remove((r, c))
40
      for r in range(ROWS):
          for c in range(COLS):
              dfs(r, c, root, "")
44
      return list(res)

Step-by-Step Solution

1

Build a Trie to Represent All Words for Prefix-Based Pruning

2def __init__(self):
  self.children = {}
  self.is_word = False
6def add_word(self, word):
  curr = self
  for c in word:
      if c not in curr.children:
          curr.children[c] = TrieNode()
      curr = curr.children[c]
  curr.is_word = True
15def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
  root = TrieNode()
  for w in words:
      root.add_word(w)

Objective

To construct a prefix tree that encodes all words, enabling efficient prefix checks during DFS.

Key Insight

Building a Trie consolidates all words into a single data structure where common prefixes are shared. This allows the search to quickly determine if the current path can lead to any word by checking if the next character exists in the Trie node's children. This shared prefix structure is essential to prune invalid paths early and avoid redundant searches for each word separately.

Interview Quick-Check

Core Logic

The Trie stores all words such that each node represents a prefix; checking if a character exists in children determines if the path is valid.

Common Pitfalls & Bugs

Forgetting to mark the end of a word with a flag (is_word) causes the algorithm to miss valid words during DFS.

2

Perform DFS with Backtracking to Explore Valid Paths on the Board

To recursively explore all valid paths on the board that match prefixes in the Trie, collecting complete words found.

3

Initiate DFS from Every Cell to Find All Words

To start the backtracking search from each cell on the board, ensuring all possible starting points are considered.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 39 Critical

visit.remove((r, c))

Remove the current cell from visited to backtrack.

This state restoration is the single most critical line in the backtracking algorithm; it ensures that the visited set correctly reflects the current path, allowing other DFS branches to explore the cell without false blockage.

Line 12 Critical

curr.is_word = True

Mark the final trie node as a complete word.

After all characters are inserted, this flag marks the path as a complete word that can be reported during DFS.

Line 23 Critical

def dfs(r, c, node, word):

Define the DFS function to explore board paths matching Trie prefixes.

DFS recursively explores neighbors, pruning paths that do not match any prefix in the Trie.

Full line-by-line criticality + rationale for all 35 lines available on Pro.

Test Your Understanding

Why is using a Trie critical for pruning the DFS search space when searching for multiple words on the board?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Word Search II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Word Search II drill

or drill a free problem

1	`class TrieNode:`
2	`def __init__(self):`
3	`self.children = {}`
4	`self.is_word = False`
5
6	`def add_word(self, word):`
7	`curr = self`
8	`for c in word:`
9	`if c not in curr.children:`
10	`curr.children[c] = TrieNode()`
11	`curr = curr.children[c]`
12	`curr.is_word = True`
13
14	`class Solution:`
15	`def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:`
16	`root = TrieNode()`
17	`for w in words:`
18	`root.add_word(w)`
19
20	`ROWS, COLS = len(board), len(board[0])`
21	`res, visit = set(), set()`
22
23	`def dfs(r, c, node, word):`
24	`if (r < 0 or c < 0 or`
25	`r == ROWS or c == COLS or`
26	`(r, c) in visit or board[r][c] not in node.children):`
27	`return`
28
29	`visit.add((r, c))`
30	`node = node.children[board[r][c]]`
31	`word += board[r][c]`
32	`if node.is_word:`
33	`res.add(word)`
34
35	`dfs(r + 1, c, node, word)`
36	`dfs(r - 1, c, node, word)`
37	`dfs(r, c + 1, node, word)`
38	`dfs(r, c - 1, node, word)`
39	`visit.remove((r, c))`
40
41	`for r in range(ROWS):`
42	`for c in range(COLS):`
43	`dfs(r, c, root, "")`
44
45	`return list(res)`

2	`def __init__(self):`
3	`self.children = {}`
4	`self.is_word = False`
6	`def add_word(self, word):`
7	`curr = self`
8	`for c in word:`
9	`if c not in curr.children:`
10	`curr.children[c] = TrieNode()`
11	`curr = curr.children[c]`
12	`curr.is_word = True`
15	`def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:`
16	`root = TrieNode()`
17	`for w in words:`
18	`root.add_word(w)`