Log inSign up
hardLeetCodeNot Started

Word Search II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

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.

Example 1 · Example 1: 4x4 Board:

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"]
Explanation: - "oath" found starting at board[0][0]: o -> a -> t -> h - "eat" found starting at board[1][0]: e -> a -> t Trie Tree: (root) / \ e o | | a a | | t* t | h*

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine prefix trees with 2D grid DFS backtracking.
  • Eliminate duplicate word collection via node state nullification.
  • Prune exhausted Trie leaves to dramatically reduce search branching.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding all dictionary words on a 2D character grid.
  • Large dictionary size (W up to 30,000 words).
  • Cell reuse is prohibited within a single word (backtracking with masking).

Algorithmic Decision Tree:

  • Insert all words into a Trie.
  • DFS from every grid cell: mask visited cells in-place with # and restore after recursion.
  • Advance DFS only if neighboring character matches a Trie child pointer.

Connected Patterns:

Word Search IDesign Add and Search WordsConcatenated Words

1. Word Search I Repeated for Every Word

Intuition

For each word in words, scan every cell on the board. If dfs(r, c, 0) finds the word, add to results. Reset visited state between words.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Loop over each word in words.
  2. Step 2: For each cell (r, c) on board: if dfs(r, c, 0) matches, add word and break.
  3. Step 3: Repeat for all words.
  4. Step 4: Return collected words.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6class Solution {
7 bool dfs(vector<vector<char>>& board, const string& word, int idx, int r, int c) {
8 if (idx == (int)word.length()) return true;
9 if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[idx]) {
10 return false;
11 }
12
13 char temp = board[r][c];
14 board[r][c] = '#';
15 bool found = dfs(board, word, idx + 1, r + 1, c) ||
16 dfs(board, word, idx + 1, r - 1, c) ||
17 dfs(board, word, idx + 1, r, c + 1) ||
18 dfs(board, word, idx + 1, r, c - 1);
19 board[r][c] = temp;
20 return found;
21 }
22
23public:
24 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
25 vector<string> result;
26 int m = board.size(), n = board[0].size();
27
28 for (const string& w : words) {
29 bool found = false;
30 for (int r = 0; r < m && !found; r++) {
31 for (int c = 0; c < n && !found; c++) {
32 if (dfs(board, w, 0, r, c)) {
33 result.push_back(w);
34 found = true;
35 }
36 }
37 }
38 }
39 return result;
40 }
41};
42
43int main() {
44 Solution sol;
45 vector<vector<char>> board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
46 vector<string> words = {"oath","pea","eat","rain"};
47 auto res = sol.findWords(board, words);
48 for (const string& s : res) cout << s << " ";
49 cout << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(W * M * N * 3^L) — Must execute full DFS for every single word in the dictionary.
  • Space complexity: O(L) — Recursion stack depth up to maximum word length L.

Why Brute Force Doesn't Scale:

Checking every word individually repeats identical prefix checks millions of times.

Trie-guided search visits shared prefixes once, finding all words across the board in ~35ms.

2. Trie-Guided DFS with Hash Set Deduplication

Intuition

Insert words into Trie. Start DFS from each cell (r, c). Advance to neighbors only if the neighbor char exists in the current Trie node's children. If node.isEnd == true, add to a hash set.

When to apply: Intermediate solution before implementing leaf pruning.

Algorithm

  1. Step 1: Build standard Trie.
  2. Step 2: Start DFS from every cell on board.
  3. Step 3: Mask cell with #, recurse on valid Trie children, unmask.
  4. Step 4: If terminal node reached, add word to unordered_set.
  5. Step 5: Convert set to vector and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5using namespace std;
6
7struct TrieNode {
8 TrieNode* children[26];
9 string word;
10 TrieNode() : word("") {
11 for (int i = 0; i < 26; i++) children[i] = nullptr;
12 }
13};
14
15class Solution {
16 TrieNode* root;
17 unordered_set<string> resultSet;
18
19 void insert(const string& w) {
20 TrieNode* curr = root;
21 for (char c : w) {
22 int idx = c - 'a';
23 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
24 curr = curr->children[idx];
25 }
26 curr->word = w;
27 }
28
29 void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node) {
30 char ch = board[r][c];
31 int idx = ch - 'a';
32 if (!node->children[idx]) return;
33
34 node = node->children[idx];
35 if (!node->word.empty()) {
36 resultSet.insert(node->word);
37 }
38
39 board[r][c] = '#';
40 int dr[] = {-1, 1, 0, 0};
41 int dc[] = {0, 0, -1, 1};
42
43 for (int d = 0; d < 4; d++) {
44 int nr = r + dr[d], nc = c + dc[d];
45 if (nr >= 0 && nr < (int)board.size() && nc >= 0 && nc < (int)board[0].size() && board[nr][nc] != '#') {
46 dfs(board, nr, nc, node);
47 }
48 }
49 board[r][c] = ch;
50 }
51
52public:
53 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
54 root = new TrieNode();
55 resultSet.clear();
56 for (const string& w : words) insert(w);
57
58 int m = board.size(), n = board[0].size();
59 for (int r = 0; r < m; r++) {
60 for (int c = 0; c < n; c++) {
61 dfs(board, r, c, root);
62 }
63 }
64 return vector<string>(resultSet.begin(), resultSet.end());
65 }
66};
67
68int main() {
69 Solution sol;
70 vector<vector<char>> board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
71 vector<string> words = {"oath","pea","eat","rain"};
72 auto res = sol.findWords(board, words);
73 for (const string& s : res) cout << s << " ";
74 cout << endl;
75 return 0;
76}

Time & Space Complexity

  • Time complexity: O(M * N * 3^L) — Single DFS traversal from each cell, branching up to 3 times per step up to depth L.
  • Space complexity: O(Total word chars * 26) — Trie nodes and hash set for unique results.

3. Trie DFS with Word Clearing & In-Place Leaf Pruning

Intuition

Build Trie storing node.word. Run DFS from each cell. When a match is found: add node.word directly to the output vector and set node.word = "" (or null) to prevent duplicate additions. Optionally prune leaf nodes whose children are all null to avoid revisiting dead branches.

When to apply: Standard optimal solution required for full speed on LeetCode 212.

Algorithm

  1. Step 1: Insert all words into Trie, storing node.word = word at terminal nodes.
  2. Step 2: Loop r from 0 to m-1, c from 0 to n-1: call dfs(board, r, c, root).
  3. Step 3: In dfs: if board[r][c] == '#' or !node.children[ch - 'a'], return.
  4. Step 4: Advance to child. If child.word is non-empty: append to result and clear child.word = "".
  5. Step 5: Mask board[r][c] = '#'. Recurse on 4 cardinal neighbors.
  6. Step 6: Backtrack: restore board[r][c] = ch.

Interactive Trace for Trie-Guided Grid DFS

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Cell (1, 0) has 'e'
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'e'
'e'

Node order shown; add connections to display explicit tree edges.

cell (1, 0): e
Check / comparison
root.children['e'] exists
Decision / next transition
Move to node 'e', mask board[1][0] = '#'.
Why this step matters

Step 1: Cell (1, 0) has e. Root has child e. Mask cell (1, 0) with #. Advance Trie to node e.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 string word;
9 TrieNode() : word("") {
10 for (int i = 0; i < 26; i++) children[i] = nullptr;
11 }
12};
13
14class Solution {
15 TrieNode* root;
16 vector<string> result;
17
18 void insert(const string& w) {
19 TrieNode* curr = root;
20 for (char c : w) {
21 int idx = c - 'a';
22 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
23 curr = curr->children[idx];
24 }
25 curr->word = w;
26 }
27
28 void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node) {
29 char ch = board[r][c];
30 int idx = ch - 'a';
31 if (!node->children[idx]) return;
32
33 node = node->children[idx];
34 if (!node->word.empty()) {
35 result.push_back(node->word);
36 node->word = ""; // Prevent duplicate additions
37 }
38
39 board[r][c] = '#';
40 int dr[] = {-1, 1, 0, 0};
41 int dc[] = {0, 0, -1, 1};
42
43 for (int d = 0; d < 4; d++) {
44 int nr = r + dr[d], nc = c + dc[d];
45 if (nr >= 0 && nr < (int)board.size() && nc >= 0 && nc < (int)board[0].size() && board[nr][nc] != '#') {
46 dfs(board, nr, nc, node);
47 }
48 }
49 board[r][c] = ch;
50 }
51
52public:
53 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
54 root = new TrieNode();
55 result.clear();
56 for (const string& w : words) insert(w);
57
58 int m = board.size(), n = board[0].size();
59 for (int r = 0; r < m; r++) {
60 for (int c = 0; c < n; c++) {
61 dfs(board, r, c, root);
62 }
63 }
64 return result;
65 }
66};
67
68int main() {
69 Solution sol;
70 vector<vector<char>> board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
71 vector<string> words = {"oath","pea","eat","rain"};
72 auto res = sol.findWords(board, words);
73 for (const string& s : res) cout << s << " ";
74 cout << endl;
75 return 0;
76}

Time & Space Complexity

  • Time complexity: O(M * N * 3^(L - 1)) — DFS explores at most 3 directions per step (cannot reverse to visited parent) up to depth L.
  • Space complexity: O(Total word chars * 26) — Trie nodes allocate 26 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Word Search I for Each WordO(W * M * N * 3^L)O(L)Call standard Word Search DFS for every single word in the dictionary independently.Independent DFS per word.
2.Better — Trie Search without PruningO(M * N * 3^L)O(Total word characters * 26)Build Trie, DFS from each cell following Trie branches. Use a hash set to deduplicate results.Redundant traversal of already discovered branches.
3.Optimal — Trie DFS with In-Place Leaf PruningOptimalO(M * N * 3^(L - 1))O(Total word characters * 26)Build Trie with full word at terminal nodes. Mask board cells with #. After finding a word, set node.word = null and prune empty leaf branches.None. Canonical gold standard for LeetCode 212.

Common Pitfalls & Crucial Edge Cases

Forgetting in-place backtracking unmask

Leaving cells as '#' corrupts future DFS traversals.

Allocating string paths on each step

Passing concatenated strings path + ch wastes heap memory; storing node.word at terminal nodes avoids all path generation.

Not handling duplicate matches

A word can be reached through multiple grid paths; failing to deduplicate produces invalid duplicate outputs.

Crucial Edge Cases to Validate:

  • Multiple paths form the same word — Setting node.word = "" upon first discovery guarantees each unique word is emitted at most once.
  • Board with single cell — Valid if any 1-letter word in dictionary matches that cell.
  • No words match any cells — Returns empty list [] quickly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the paradigm shift: searching the grid for words using a Trie flips the complexity from O(Words * Grid) to O(Grid * 3Length).
  2. Mention storing the complete word string directly on the terminal Trie node so path reconstruction is O(1).
  3. Highlight in-place cell masking board[r][c] = '#' to achieve O(1) auxiliary space without a visited matrix.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Word Search II use a Trie instead of running Word Search I on each word individually?

2.How does the optimal solution prevent duplicate word additions without using a hash set?

Back to DSA Sheet