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:
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: []
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j] is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i] consists of lowercase English letters.words are unique.Word Search II extends the classic board search problem by asking you to find multiple words from a list inside a 2D character grid. A naive approach would check each word independently using DFS, but this becomes inefficient when the word list is large.
The optimal strategy combines a Trie (prefix tree) with DFS backtracking. First, insert all words into a Trie so that common prefixes are shared. Then start a DFS from each cell of the board while traversing the Trie simultaneously. If the current path does not exist in the Trie, you can prune the search early. When a complete word is found, record it and optionally remove it from the Trie to avoid duplicates.
This method significantly reduces unnecessary exploration because only valid prefixes are followed. The board is explored with backtracking by marking cells as visited and restoring them after recursion. Building the Trie takes O(total characters in words), while the board search explores paths constrained by Trie prefixes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Trie + DFS Backtracking | O(M * N * 4^L) in the worst case, where MxN is the board size and L is the maximum word length, with strong pruning using Trie prefixes | O(W * L) for the Trie, where W is number of words and L is average word length, plus recursion stack |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: <a href="https://leetcode.com/problems/implement-trie-prefix-tree/">Implement Trie (Prefix Tree)</a> first.
This approach uses a Trie to represent the list of words for efficient prefix matching. The algorithm performs depth-first search (DFS) on the board starting from each cell. Each path of exploration is checked against the Trie to determine if it forms any of the words or prefixes thereof. The benefit of using a Trie is that we can stop the search early if the current path does not match any prefix in the Trie, thereby improving the efficiency of the search process.
Time Complexity: O(M*(4*3^(L-1))), where M is the number of cells on the board, and L is the maximum length of a word.
Space Complexity: O(N*L), where N is the number of words, and L is the maximum length of a word, used by the Trie structure.
1using System;
2using System.Collections.Generic;
3
4public class TrieNode {
5 public TrieNode[] Children = new TrieNode[26];
6 public string Word;
7}
8
9public class Solution {
10 public IList<string> FindWords(char[][] board, string[] words) {
11 TrieNode root = new TrieNode();
12 foreach (var word in words) InsertWord(root, word);
13 HashSet<string> result = new HashSet<string>();
14 for (int i = 0; i < board.Length; i++)
for (int j = 0; j < board[0].Length; j++)
Dfs(board, i, j, root, result);
return new List<string>(result);
}
private void InsertWord(TrieNode root, string word) {
TrieNode node = root;
foreach (var ch in word) {
if (node.Children[ch - 'a'] == null)
node.Children[ch - 'a'] = new TrieNode();
node = node.Children[ch - 'a'];
}
node.Word = word;
}
private void Dfs(char[][] board, int i, int j, TrieNode node, HashSet<string> result) {
char c = board[i][j];
if (c == '#' || node.Children[c - 'a'] == null) return;
node = node.Children[c - 'a'];
if (node.Word != null) {
result.Add(node.Word);
node.Word = null; // Avoid duplicates
}
board[i][j] = '#';
if (i > 0) Dfs(board, i - 1, j, node, result);
if (j > 0) Dfs(board, i, j - 1, node, result);
if (i < board.Length - 1) Dfs(board, i + 1, j, node, result);
if (j < board[0].Length - 1) Dfs(board, i, j + 1, node, result);
board[i][j] = c;
}
}The C# solution constructs a Trie for input words and performs DFS on the board. The Trie is traversed according to characters found during the DFS. A hash set gathers the found words to ensure uniqueness.
In this approach, we perform backtracking for each word individually. This avoids the overhead of constructing a Trie but involves repeated board scanning. A Recursive Depth First Search (DFS) is used to explore possibilities starting from each cell on the board. We maintain a visited matrix to ensure a letter is not reused in forming a particular word.
Time Complexity: O(N * M * 3^L), where N is the number of words, M is the number of cells in the board, and L is the length of the word being searched in the worst case.
Space Complexity: O(L), for the recursive call stack.
public bool Exist(char[][] board, string word) {
for (int i = 0; i < board.Length; i++) {
for (int j = 0; j < board[0].Length; j++) {
if (Dfs(board, word, i, j, 0, new bool[board.Length, board[0].Length])) {
return true;
}
}
}
return false;
}
private bool Dfs(char[][] board, string word, int i, int j, int index, bool[,] visited) {
if (index == word.Length) return true;
if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length) return false;
if (visited[i, j] || board[i][j] != word[index]) return false;
visited[i, j] = true;
if (Dfs(board, word, i + 1, j, index + 1, visited) ||
Dfs(board, word, i - 1, j, index + 1, visited) ||
Dfs(board, word, i, j + 1, index + 1, visited) ||
Dfs(board, word, i, j - 1, index + 1, visited)) {
return true;
}
visited[i, j] = false;
return false;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Word Search II is considered a classic hard interview problem and has appeared in FAANG-style interviews. It tests knowledge of Tries, DFS backtracking, pruning techniques, and efficient grid traversal.
A Trie (prefix tree) is the most effective data structure for this problem. It allows efficient prefix checks while exploring the grid and enables early stopping when a path cannot lead to a valid word.
The optimal approach uses a Trie combined with DFS backtracking. All words are inserted into a Trie so the search can follow only valid prefixes while exploring the board. This significantly prunes unnecessary paths compared to searching each word independently.
Checking each word separately would require running DFS for every word, which becomes very slow for large word lists. A Trie merges common prefixes so the board is traversed once while simultaneously matching multiple words.
This C# implementation uses a grid search with a depth-first approach, utilizing a 2D array to track visited cells. By recursively exploring all directions, it determines the presence of the word on the board.