LeetCode 212: Word Search II (Trie + DFS Backtracking Pruning)
LeetCode 212TrieBacktrackingGrid DFSToday we solve LeetCode 212 - Word Search II.
Source: https://leetcode.com/problems/word-search-ii/
English
Problem Summary
Given a 2D board of characters and a list of words, return all words that can be formed by traversing adjacent cells (up/down/left/right) without reusing a cell in one word path.
Key Insight
If we run DFS separately for each word, we repeat huge amounts of prefix work. A Trie stores all words together so each DFS step can prune immediately when the current prefix does not exist in the dictionary.
Brute Force and Limitations
Brute force does: for each word, run board DFS search. With many words sharing prefixes, this duplicates traversal and can time out badly. Trie + one board scan shares prefix checks and cuts dead branches early.
Optimal Algorithm Steps
1) Build a Trie from all words; mark complete words at terminal nodes.
2) Start DFS from every board cell, but only continue if character exists in current Trie node.
3) On reaching a Trie node with a stored word, add it to answer and clear it to avoid duplicates.
4) Mark current board cell as visited (#), explore 4 directions, then restore cell.
5) Optional pruning: if a Trie node becomes empty after search, detach it from parent.
Complexity Analysis
Let m*n be board size and S be total word characters in Trie.
Building Trie: O(S).
DFS: worst-case upper bound is high (O(m*n*4^L), L max word length), but Trie pruning dramatically reduces practical work.
Extra Space: O(S + L) for Trie plus recursion stack depth.
Common Pitfalls
- Forgetting to restore board cell after DFS backtracking.
- Returning duplicate words because terminal marker is not cleared after first hit.
- Running DFS for each word instead of Trie-sharing prefixes.
- Missing boundary checks before board access.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
List<String> ans = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
dfs(board, r, c, root, ans);
}
}
return ans;
}
private void dfs(char[][] board, int r, int c, TrieNode node, List<String> ans) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;
char ch = board[r][c];
if (ch == '#') return;
TrieNode nextNode = node.next[ch - 'a'];
if (nextNode == null) return;
if (nextNode.word != null) {
ans.add(nextNode.word);
nextNode.word = null; // avoid duplicates
}
board[r][c] = '#';
dfs(board, r + 1, c, nextNode, ans);
dfs(board, r - 1, c, nextNode, ans);
dfs(board, r, c + 1, nextNode, ans);
dfs(board, r, c - 1, nextNode, ans);
board[r][c] = ch;
// optional pruning: if this node became useless, parent paths can stop earlier
if (isLeaf(nextNode) && nextNode.word == null) {
node.next[ch - 'a'] = null;
}
}
private boolean isLeaf(TrieNode node) {
for (TrieNode child : node.next) {
if (child != null) return false;
}
return true;
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (int i = 0; i < w.length(); i++) {
int idx = w.charAt(i) - 'a';
if (cur.next[idx] == null) cur.next[idx] = new TrieNode();
cur = cur.next[idx];
}
cur.word = w;
}
return root;
}
}type TrieNode struct {
next [26]*TrieNode
word string
}
func findWords(board [][]byte, words []string) []string {
root := buildTrie(words)
ans := make([]string, 0)
rows, cols := len(board), len(board[0])
var dfs func(int, int, *TrieNode)
dfs = func(r, c int, node *TrieNode) {
if r < 0 || c < 0 || r >= rows || c >= cols {
return
}
ch := board[r][c]
if ch == '#' {
return
}
nxt := node.next[ch-'a']
if nxt == nil {
return
}
if nxt.word != "" {
ans = append(ans, nxt.word)
nxt.word = ""
}
board[r][c] = '#'
dfs(r+1, c, nxt)
dfs(r-1, c, nxt)
dfs(r, c+1, nxt)
dfs(r, c-1, nxt)
board[r][c] = ch
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
dfs(r, c, root)
}
}
return ans
}
func buildTrie(words []string) *TrieNode {
root := &TrieNode{}
for _, w := range words {
cur := root
for i := 0; i < len(w); i++ {
idx := w[i] - 'a'
if cur.next[idx] == nil {
cur.next[idx] = &TrieNode{}
}
cur = cur.next[idx]
}
cur.word = w
}
return root
}class Solution {
struct TrieNode {
TrieNode* next[26]{};
string word;
};
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode* root = buildTrie(words);
vector<string> ans;
for (int r = 0; r < (int)board.size(); ++r) {
for (int c = 0; c < (int)board[0].size(); ++c) {
dfs(board, r, c, root, ans);
}
}
return ans;
}
private:
void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node, vector<string>& ans) {
if (r < 0 || c < 0 || r >= (int)board.size() || c >= (int)board[0].size()) return;
char ch = board[r][c];
if (ch == '#') return;
TrieNode* nxt = node->next[ch - 'a'];
if (!nxt) return;
if (!nxt->word.empty()) {
ans.push_back(nxt->word);
nxt->word.clear();
}
board[r][c] = '#';
dfs(board, r + 1, c, nxt, ans);
dfs(board, r - 1, c, nxt, ans);
dfs(board, r, c + 1, nxt, ans);
dfs(board, r, c - 1, nxt, ans);
board[r][c] = ch;
}
TrieNode* buildTrie(vector<string>& words) {
TrieNode* root = new TrieNode();
for (auto& w : words) {
TrieNode* cur = root;
for (char ch : w) {
int idx = ch - 'a';
if (!cur->next[idx]) cur->next[idx] = new TrieNode();
cur = cur->next[idx];
}
cur->word = w;
}
return root;
}
};class TrieNode:
def __init__(self):
self.next = {}
self.word = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
cur = root
for ch in w:
if ch not in cur.next:
cur.next[ch] = TrieNode()
cur = cur.next[ch]
cur.word = w
rows, cols = len(board), len(board[0])
ans = []
def dfs(r: int, c: int, node: TrieNode) -> None:
if r < 0 or c < 0 or r >= rows or c >= cols:
return
ch = board[r][c]
if ch == '#' or ch not in node.next:
return
nxt = node.next[ch]
if nxt.word is not None:
ans.append(nxt.word)
nxt.word = None
board[r][c] = '#'
dfs(r + 1, c, nxt)
dfs(r - 1, c, nxt)
dfs(r, c + 1, nxt)
dfs(r, c - 1, nxt)
board[r][c] = ch
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return ansvar findWords = function(board, words) {
class TrieNode {
constructor() {
this.next = new Map();
this.word = null;
}
}
const root = new TrieNode();
for (const w of words) {
let cur = root;
for (const ch of w) {
if (!cur.next.has(ch)) cur.next.set(ch, new TrieNode());
cur = cur.next.get(ch);
}
cur.word = w;
}
const rows = board.length, cols = board[0].length;
const ans = [];
const dfs = (r, c, node) => {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
const ch = board[r][c];
if (ch === '#' || !node.next.has(ch)) return;
const nxt = node.next.get(ch);
if (nxt.word !== null) {
ans.push(nxt.word);
nxt.word = null;
}
board[r][c] = '#';
dfs(r + 1, c, nxt);
dfs(r - 1, c, nxt);
dfs(r, c + 1, nxt);
dfs(r, c - 1, nxt);
board[r][c] = ch;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root);
}
}
return ans;
};中文
题目概述
给定一个字符网格和单词列表，要求找出所有能在网格中通过上下左右相邻格子拼出的单词；同一个单词路径中同一格不能重复使用。
核心思路
如果“每个单词都单独做一次 DFS”，会重复大量前缀搜索。把所有单词放进 Trie 后，DFS 过程中只要当前前缀不在 Trie 中就立刻剪枝，性能会稳定很多。
暴力解法与不足
暴力方式是：遍历每个单词，再在整张板子上找路径。单词数量大、前缀重叠多时，会重复遍历同样的路径，容易超时。
最优算法步骤
1）先把所有单词构造成 Trie，终止节点保存完整单词。
2）从每个格子发起 DFS，只有当前字符在 Trie 子节点中才继续。
3）到达含有完整单词的节点就加入答案，并清空该标记避免重复收集。
4）把当前格临时标记为 # 表示已访问，搜索四个方向后恢复原字符。
5）可选：若某 Trie 节点已无子节点且不再代表单词，可从父节点断开进一步剪枝。
复杂度分析
设网格大小为 m*n，所有单词总长度为 S。
建 Trie 复杂度：O(S)。
DFS 最坏上界仍可能较高（O(m*n*4^L)，L 为最大单词长度），但 Trie 剪枝在实际数据上通常能显著降低搜索量。
额外空间：O(S + L)（Trie + 递归栈）。
常见陷阱
- 回溯后忘记恢复网格字符。
- 命中单词后不清空标记，导致重复答案。
- 仍按“单词维度”做 DFS，没利用 Trie 的共享前缀。
- 边界判断顺序错误导致越界访问。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
List<String> ans = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
dfs(board, r, c, root, ans);
}
}
return ans;
}
private void dfs(char[][] board, int r, int c, TrieNode node, List<String> ans) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;
char ch = board[r][c];
if (ch == '#') return;
TrieNode nextNode = node.next[ch - 'a'];
if (nextNode == null) return;
if (nextNode.word != null) {
ans.add(nextNode.word);
nextNode.word = null; // avoid duplicates
}
board[r][c] = '#';
dfs(board, r + 1, c, nextNode, ans);
dfs(board, r - 1, c, nextNode, ans);
dfs(board, r, c + 1, nextNode, ans);
dfs(board, r, c - 1, nextNode, ans);
board[r][c] = ch;
// optional pruning: if this node became useless, parent paths can stop earlier
if (isLeaf(nextNode) && nextNode.word == null) {
node.next[ch - 'a'] = null;
}
}
private boolean isLeaf(TrieNode node) {
for (TrieNode child : node.next) {
if (child != null) return false;
}
return true;
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (int i = 0; i < w.length(); i++) {
int idx = w.charAt(i) - 'a';
if (cur.next[idx] == null) cur.next[idx] = new TrieNode();
cur = cur.next[idx];
}
cur.word = w;
}
return root;
}
}type TrieNode struct {
next [26]*TrieNode
word string
}
func findWords(board [][]byte, words []string) []string {
root := buildTrie(words)
ans := make([]string, 0)
rows, cols := len(board), len(board[0])
var dfs func(int, int, *TrieNode)
dfs = func(r, c int, node *TrieNode) {
if r < 0 || c < 0 || r >= rows || c >= cols {
return
}
ch := board[r][c]
if ch == '#' {
return
}
nxt := node.next[ch-'a']
if nxt == nil {
return
}
if nxt.word != "" {
ans = append(ans, nxt.word)
nxt.word = ""
}
board[r][c] = '#'
dfs(r+1, c, nxt)
dfs(r-1, c, nxt)
dfs(r, c+1, nxt)
dfs(r, c-1, nxt)
board[r][c] = ch
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
dfs(r, c, root)
}
}
return ans
}
func buildTrie(words []string) *TrieNode {
root := &TrieNode{}
for _, w := range words {
cur := root
for i := 0; i < len(w); i++ {
idx := w[i] - 'a'
if cur.next[idx] == nil {
cur.next[idx] = &TrieNode{}
}
cur = cur.next[idx]
}
cur.word = w
}
return root
}class Solution {
struct TrieNode {
TrieNode* next[26]{};
string word;
};
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode* root = buildTrie(words);
vector<string> ans;
for (int r = 0; r < (int)board.size(); ++r) {
for (int c = 0; c < (int)board[0].size(); ++c) {
dfs(board, r, c, root, ans);
}
}
return ans;
}
private:
void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node, vector<string>& ans) {
if (r < 0 || c < 0 || r >= (int)board.size() || c >= (int)board[0].size()) return;
char ch = board[r][c];
if (ch == '#') return;
TrieNode* nxt = node->next[ch - 'a'];
if (!nxt) return;
if (!nxt->word.empty()) {
ans.push_back(nxt->word);
nxt->word.clear();
}
board[r][c] = '#';
dfs(board, r + 1, c, nxt, ans);
dfs(board, r - 1, c, nxt, ans);
dfs(board, r, c + 1, nxt, ans);
dfs(board, r, c - 1, nxt, ans);
board[r][c] = ch;
}
TrieNode* buildTrie(vector<string>& words) {
TrieNode* root = new TrieNode();
for (auto& w : words) {
TrieNode* cur = root;
for (char ch : w) {
int idx = ch - 'a';
if (!cur->next[idx]) cur->next[idx] = new TrieNode();
cur = cur->next[idx];
}
cur->word = w;
}
return root;
}
};class TrieNode:
def __init__(self):
self.next = {}
self.word = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
cur = root
for ch in w:
if ch not in cur.next:
cur.next[ch] = TrieNode()
cur = cur.next[ch]
cur.word = w
rows, cols = len(board), len(board[0])
ans = []
def dfs(r: int, c: int, node: TrieNode) -> None:
if r < 0 or c < 0 or r >= rows or c >= cols:
return
ch = board[r][c]
if ch == '#' or ch not in node.next:
return
nxt = node.next[ch]
if nxt.word is not None:
ans.append(nxt.word)
nxt.word = None
board[r][c] = '#'
dfs(r + 1, c, nxt)
dfs(r - 1, c, nxt)
dfs(r, c + 1, nxt)
dfs(r, c - 1, nxt)
board[r][c] = ch
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return ansvar findWords = function(board, words) {
class TrieNode {
constructor() {
this.next = new Map();
this.word = null;
}
}
const root = new TrieNode();
for (const w of words) {
let cur = root;
for (const ch of w) {
if (!cur.next.has(ch)) cur.next.set(ch, new TrieNode());
cur = cur.next.get(ch);
}
cur.word = w;
}
const rows = board.length, cols = board[0].length;
const ans = [];
const dfs = (r, c, node) => {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
const ch = board[r][c];
if (ch === '#' || !node.next.has(ch)) return;
const nxt = node.next.get(ch);
if (nxt.word !== null) {
ans.push(nxt.word);
nxt.word = null;
}
board[r][c] = '#';
dfs(r + 1, c, nxt);
dfs(r - 1, c, nxt);
dfs(r, c + 1, nxt);
dfs(r, c - 1, nxt);
board[r][c] = ch;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root);
}
}
return ans;
};
Comments