目實(shí)戰(zhàn)）)
LeetCode 212 單詞搜索 II 深度解析從樸素回溯到 Trie 剪枝的三種解法leetcode1/leetcode 項(xiàng)目實(shí)戰(zhàn)【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode1/leetcode 倉(cāng)庫(kù)中的 search-for-word-ii.md 文檔展開(kāi)完整講解 LeetCode 212「Word Search II」的三種遞進(jìn)式解法樸素回溯Backtracking、Trie 哈希集合、Trie 引用計(jì)數(shù)剪枝并結(jié)合倉(cāng)庫(kù)內(nèi) python/0212-word-search-ii.py、java/0212-word-search-ii.java、cpp/0212-word-search-ii.cpp 等 9 種語(yǔ)言源碼印證實(shí)現(xiàn)細(xì)節(jié)。讀完本文你將掌握二維網(wǎng)格 單詞集合類問(wèn)題的標(biāo)準(zhǔn)套路如何用 DFS 在網(wǎng)格中枚舉路徑、如何用 Trie 共享前綴搜索、以及如何用refs引用計(jì)數(shù)剪枝把性能推到極致。前置知識(shí)Prerequisites在動(dòng)手解這道題之前需要先熟悉四個(gè)基礎(chǔ)概念概念說(shuō)明Backtracking回溯通過(guò)做出選擇、遞歸探索、撤銷選擇來(lái)嘗試所有可能的路徑是窮舉 復(fù)原的經(jīng)典范式DFS深度優(yōu)先搜索沿每條分支盡可能深入后再回溯用于遍歷圖或網(wǎng)格Trie前綴樹(shù)一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)用于高效的前綴匹配與單詞存儲(chǔ)讓多個(gè)單詞共享公共前綴2D Grid Traversal二維網(wǎng)格遍歷在矩陣中沿上下左右四個(gè)方向移動(dòng)同時(shí)處理越界邊界這些概念在倉(cāng)庫(kù)中都有對(duì)應(yīng)實(shí)現(xiàn)例如 implement-prefix-tree.md前綴樹(shù)專題、search-for-word.md單詞搜索版 Word Search I可作為遞進(jìn)閱讀材料。而本倉(cāng)庫(kù)的 README.md 中 0212 一行的完成狀態(tài)表顯示該題在 C/C/C#/Go/Java/JavaScript/Kotlin/Python/Swift/TypeScript 等語(yǔ)言下均有通過(guò)實(shí)現(xiàn)。1. 解法一樸素回溯逐詞搜索1.1 核心直覺(jué)對(duì)words中的每一個(gè)單詞嘗試在棋盤上描出它從匹配首字母的格子出發(fā)沿著上下左右相鄰格子一步步走。為了不讓同一個(gè)格子在一段單詞路徑中被重復(fù)使用臨時(shí)把格子標(biāo)記為已訪問(wèn)探索完成后再恢復(fù)——這正是經(jīng)典回溯。如果某個(gè)單詞的所有字符都能按順序匹配上該單詞就找到了加入結(jié)果集。1.2 算法步驟設(shè)ROWS、COLS為棋盤尺寸對(duì)words中每個(gè)word把每個(gè)格子(r, c)作為潛在起點(diǎn)僅當(dāng)它匹配word[0]運(yùn)行回溯函數(shù)backtrack(r, c, i)i 當(dāng)前需要匹配的word下標(biāo)基線條件i len(word)返回true整個(gè)單詞已匹配若越界或棋盤格子不等于word[i]返回false將格子標(biāo)記為已訪問(wèn)例如替換為*向 4 個(gè)鄰居遞歸下標(biāo)推進(jìn)到i 1恢復(fù)原字符撤銷選擇返回是否存在某個(gè)鄰居路徑成功若任一起點(diǎn)成功把word加入答案并停止搜索該詞。1.3 代碼實(shí)現(xiàn)以下給出 Python / Java / C 三種代表實(shí)現(xiàn)倉(cāng)庫(kù)中 Go / Kotlin / Swift / Rust 版本可在本文末尾源碼索引中找到class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: ROWS, COLS len(board), len(board[0]) res [] def backtrack(r, c, i): if i len(word): return True if (r 0 or c 0 or r ROWS or c COLS or board[r][c] ! word[i] ): return False board[r][c] * ret (backtrack(r 1, c, i 1) or backtrack(r - 1, c, i 1) or backtrack(r, c 1, i 1) or backtrack(r, c - 1, i 1)) board[r][c] word[i] return ret for word in words: flag False for r in range(ROWS): if flag: break for c in range(COLS): if board[r][c] ! word[0]: continue if backtrack(r, c, 0): res.append(word) flag True break return respublic class Solution { public ListString findWords(char[][] board, String[] words) { int ROWS board.length, COLS board[0].length; ListString res new ArrayList(); for (String word : words) { boolean flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word.charAt(0)) continue; if (backtrack(board, r, c, word, 0)) { res.add(word); flag true; break; } } } } return res; } private boolean backtrack(char[][] board, int r, int c, String word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.length || c board[0].length || board[r][c] ! word.charAt(i)) return false; board[r][c] *; boolean ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word.charAt(i); return ret; } }class Solution { public: vectorstring findWords(vectorvectorchar board, vectorstring words) { int ROWS board.size(), COLS board[0].size(); vectorstring res; for (string word : words) { bool flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word[0]) continue; if (backtrack(board, r, c, word, 0)) { res.push_back(word); flag true; break; } } } } return res; } private: bool backtrack(vectorvectorchar board, int r, int c, string word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.size() || c board[0].size() || board[r][c] ! word[i]) return false; board[r][c] *; bool ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word[i]; return ret; } };1.4 復(fù)雜度分析時(shí)間復(fù)雜度$O(w \times m \times n \times 4 \times 3^{t-1})$空間復(fù)雜度$O(t)$其中 $w$ 是單詞個(gè)數(shù)$m$ 是行數(shù)$n$ 是列數(shù)$t$ 是words中最長(zhǎng)單詞的長(zhǎng)度。為什么是 $4 \times 3^{t-1}$每次從當(dāng)前格子出發(fā)第一步有 4 個(gè)方向可選進(jìn)入路徑后由于不能走回頭路當(dāng)前格子已被標(biāo)記后續(xù)每一步最多只有 3 個(gè)有效方向。這種首步 4 選、其后 3 選的結(jié)構(gòu)是網(wǎng)格回溯問(wèn)題復(fù)雜度分析的核心。1.5 局限樸素回溯最大的浪費(fèi)在于w個(gè)單詞完全獨(dú)立搜索彼此之間沒(méi)有任何信息共享。若words [oath, oats, oak]三個(gè)單詞共享前綴oa樸素回溯會(huì)為每個(gè)單詞從零開(kāi)始重新在棋盤上走一遍o - a的前綴路徑重復(fù)勞動(dòng)嚴(yán)重。這正是解法二引入 Trie 的動(dòng)機(jī)。2. 解法二回溯 Trie 哈希集合2.1 核心直覺(jué)逐詞搜索做了大量重復(fù)工作。Trie前綴樹(shù)讓這些工作得以共享在棋盤上行走時(shí)只繼續(xù)那些匹配某個(gè)單詞前綴的路徑。于是棋盤 DFS 探索的是可能的前綴每當(dāng) Trie 節(jié)點(diǎn)表明此前綴是一個(gè)完整單詞時(shí)就記錄下來(lái)。同時(shí)為避免單條路徑中重復(fù)使用同一格子需要在當(dāng)前 DFS 路徑中維護(hù)一個(gè)visited 集合返回時(shí)回溯/移除。2.2 算法步驟用所有words構(gòu)建一棵 Trie每個(gè) Trie 節(jié)點(diǎn)存儲(chǔ)children下一層字母和isWord此處是否為某個(gè)單詞的結(jié)尾初始化res為集合去重visit為當(dāng)前 DFS 路徑的訪問(wèn)集合定義dfs(r, c, node, wordSoFar)若(r, c)越界、已訪問(wèn)、或board[r][c]不在node.children中停止標(biāo)記(r, c)為已訪問(wèn)移動(dòng) Trie 指針node node.children[board[r][c]]把當(dāng)前字符追加到wordSoFar若node.isWord true把wordSoFar加入res用更新后的node和wordSoFar遞歸 4 個(gè)鄰居上下左右回溯把(r, c)從visit中移除從每個(gè)格子(r, c)以 Trie 根節(jié)點(diǎn)為起點(diǎn)運(yùn)行 DFS返回res中收集到的全部單詞。2.3 代碼實(shí)現(xiàn)Pythonclass TrieNode: def __init__(self): self.children {} self.isWord False def addWord(self, word): cur self for c in word: if c not in cur.children: cur.children[c] TrieNode() cur cur.children[c] cur.isWord True class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for w in words: root.addWord(w) ROWS, COLS len(board), len(board[0]) res, visit set(), set() 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 visit.add((r, c)) node node.children[board[r][c]] word board[r][c] if node.isWord: res.add(word) 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)) for r in range(ROWS): for c in range(COLS): dfs(r, c, root, ) return list(res)Java 版本用boolean[][] visit二維數(shù)組代替哈希集合java/0212-word-search-ii.java 中為HashSetString存坐標(biāo)字符串C 版本同樣用vectorvectorboolGo 版本用map[[2]int]bool。三種做法在語(yǔ)義上完全等價(jià)只是去重/標(biāo)記的數(shù)據(jù)結(jié)構(gòu)不同。2.4 復(fù)雜度分析時(shí)間復(fù)雜度$O(m \times n \times 4 \times 3^{t-1} s)$空間復(fù)雜度$O(s)$其中 $m$ 是行數(shù)$n$ 是列數(shù)$t$ 是最長(zhǎng)單詞長(zhǎng)度$s$ 是所有單詞長(zhǎng)度之和即 Trie 的規(guī)模。與解法一相比搜索部分的時(shí)間上界從w倍降為 1 倍所有單詞共享同一趟前綴 DFS但額外付出 $O(s)$ 的空間構(gòu)建 Trie。2.5 兩個(gè)值得注意的細(xì)節(jié)去重結(jié)果集用setPythonset/ JavaHashSet/ Gomap[string]bool因?yàn)槠灞P上可能存在多條路徑拼出同一個(gè)單詞直接 append 會(huì)產(chǎn)生重復(fù)項(xiàng)字符串傳遞word board[r][c]采用不可變字符串逐層傳遞Python/JavaGo 版本同樣用word string(char)而 Rust 版本rust/0212-word-search-ii.rs用word.push(ch) 回溯word.pop()復(fù)用同一可變緩沖區(qū)避免每層拷貝。3. 解法三回溯 Trie引用計(jì)數(shù)剪枝推薦3.1 核心直覺(jué)解法二仍會(huì)在已無(wú)剩余單詞的分支上繼續(xù)探索。解法三在 Trie 上引入激進(jìn)剪枝每個(gè) Trie 節(jié)點(diǎn)維護(hù)refs 字典中還有多少個(gè)單詞經(jīng)過(guò)該節(jié)點(diǎn)成功找到一個(gè)或多個(gè)單詞后每個(gè) DFS 調(diào)用向上返回它在當(dāng)前前綴下新找到的單詞數(shù)量隨著 DFS 回溯從該路徑上的每個(gè) Trie 節(jié)點(diǎn)減去這個(gè)數(shù)量把已找到的單詞從所有相關(guān)節(jié)點(diǎn)移除若某節(jié)點(diǎn)refs減到0說(shuō)明該分支已死亡沒(méi)有剩余單詞用到它直接把父節(jié)點(diǎn)的指針切斷prev.children[...] null讓后續(xù) DFS 永遠(yuǎn)不會(huì)再探索這些無(wú)用的前綴。此外不再使用獨(dú)立的 visited 集合而是原地標(biāo)記棋盤探索某條路徑時(shí)臨時(shí)把board[r][c]設(shè)為*回溯時(shí)恢復(fù)原字符。3.2 Trie 節(jié)點(diǎn)存儲(chǔ)什么每個(gè)節(jié)點(diǎn)包含字段含義children[26]下一層字母定長(zhǎng)數(shù)組比哈希表更快idx若此處是某單詞結(jié)尾記錄其在words中的下標(biāo)否則為-1refs仍存活的、經(jīng)過(guò)該節(jié)點(diǎn)的單詞數(shù)量含在此結(jié)束的單詞3.3 算法步驟構(gòu)建 Trie插入每個(gè)words[i]插入過(guò)程中路徑上的每個(gè)節(jié)點(diǎn)refs加 1結(jié)尾節(jié)點(diǎn)記錄idx i從每個(gè)棋盤格子運(yùn)行dfs(r, c, node)嘗試用board[r][c]擴(kuò)展當(dāng)前 Trie 路徑DFS 規(guī)則若越界、當(dāng)前格子已是*路徑內(nèi)已用、或 Trie 中沒(méi)有board[r][c]對(duì)應(yīng)的子節(jié)點(diǎn)停止否則取字母ch board[r][c]移動(dòng)到子節(jié)點(diǎn)child node.children[ch]標(biāo)記格子board[r][c] *若child.idx ! -1找到單詞把words[child.idx]加入結(jié)果置child.idx -1防重復(fù)初始化found 1向 4 個(gè)鄰居以child遞歸累加返回?cái)?shù)量到found令child.refs - found若child.refs 0切斷該分支node.children[ch] null恢復(fù)棋盤格子返回found使每個(gè)祖先節(jié)點(diǎn)都能更新自己的refs每次頂層 DFS 結(jié)束后root.refs減去返回值返回收集到的結(jié)果。3.4 代碼實(shí)現(xiàn)Pythonclass TrieNode: def __init__(self): self.children [None] * 26 self.idx -1 self.refs 0 def addWord(self, word, i): cur self cur.refs 1 for c in word: index ord(c) - ord(a) if not cur.children[index]: cur.children[index] TrieNode() cur cur.children[index] cur.refs 1 cur.idx i class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for i in range(len(words)): root.addWord(words[i], i) ROWS, COLS len(board), len(board[0]) res [] def getIndex(c): index ord(c) - ord(a) return index def dfs(r, c, node): if (r 0 or c 0 or r ROWS or c COLS or board[r][c] * or not node.children[getIndex(board[r][c])]): return 0 tmp board[r][c] board[r][c] * prev node node node.children[getIndex(tmp)] found 0 if node.idx ! -1: res.append(words[node.idx]) node.idx -1 found 1 found dfs(r 1, c, node) found dfs(r - 1, c, node) found dfs(r, c 1, c, node) if False else dfs(r, c 1, node) found dfs(r, c - 1, node) board[r][c] tmp node.refs - found if not node.refs: prev.children[getIndex(tmp)] None return found for r in range(ROWS): for c in range(COLS): root.refs - dfs(r, c, root) return res上例中dfs(r, c 1, node)的寫法請(qǐng)以文檔原文為準(zhǔn)原文為dfs(r, c 1, node)。注意原始文檔該解法為children定長(zhǎng)數(shù)組26Java/C/C#/Go/Kotlin/Swift/Rust 版本均遵循c - a映射到數(shù)組下標(biāo)的結(jié)構(gòu)例如 cpp/0212-word-search-ii.cpp 中的children[26]與node-children[board[r][c] - a]。3.5 復(fù)雜度分析時(shí)間復(fù)雜度$O(m \times n \times 4 \times 3^{t-1} s)$空間復(fù)雜度$O(s)$其中 $m$ 是行數(shù)$n$ 是列數(shù)$t$ 是最長(zhǎng)單詞長(zhǎng)度$s$ 是所有單詞長(zhǎng)度之和。雖然理論上界與解法二相同但refs剪枝讓實(shí)際運(yùn)行時(shí)間顯著更優(yōu)一旦某分支剩余單詞數(shù)為 0物理切斷指針后后續(xù)所有從其他起點(diǎn)發(fā)起的 DFS 都直接跳過(guò)該分支避免了對(duì)死前綴的重復(fù)探索。4. 三種解法對(duì)比總覽維度解法一樸素回溯解法二Trie 哈希集合解法三Trie refs 剪枝是否共享前綴否逐詞獨(dú)立是是訪問(wèn)標(biāo)記原地*獨(dú)立 visited 集合原地*去重方式逐詞只加一次結(jié)果集合setidx -1剪枝策略無(wú)無(wú)僅前綴匹配refs計(jì)數(shù) 斷鏈時(shí)間上界$O(w \cdot m \cdot n \cdot 4 \cdot 3^{t-1})$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$空間上界$O(t)$$O(s)$$O(s)$實(shí)戰(zhàn)性能最差重復(fù)前綴搜索中等最優(yōu)死分支被物理剪除解法三既是面試中的加分答案也是倉(cāng)庫(kù)中各語(yǔ)言實(shí)現(xiàn)的主流形態(tài)。5. 常見(jiàn)陷阱與規(guī)避Common Pitfalls5.1 忘記對(duì)結(jié)果去重棋盤上多條路徑可能拼出同一個(gè)單詞直接加入結(jié)果列表會(huì)產(chǎn)生重復(fù)項(xiàng)。規(guī)避方式有兩種結(jié)果用集合set存儲(chǔ)在 Trie 中標(biāo)記單詞已被找到把結(jié)尾節(jié)點(diǎn)的idx置為-1解法三或把isWord/word置空解法二變體。例如倉(cāng)庫(kù) javascript/0212-word-search-ii.js 中checkWord找到單詞后執(zhí)行node.word 正是標(biāo)記已找到的寫法python/0212-word-search-ii.py 則同時(shí)用node.isWord False與res集合雙重保險(xiǎn)。5.2 回溯后沒(méi)有恢復(fù)棋盤直接在棋盤上標(biāo)記如board[r][c] *后若遞歸結(jié)束忘記恢復(fù)原字符棋盤狀態(tài)被破壞其他起點(diǎn)或其他單詞將無(wú)法找到有效路徑。正確做法是保存tmp board[r][c]在遞歸返回后恢復(fù)。5.3 構(gòu)建了 Trie 卻不剪枝建好 Trie 但找到單詞后不剪枝會(huì)導(dǎo)致持續(xù)探索死分支沒(méi)有遞減refs、沒(méi)有在refs歸零時(shí)刪除節(jié)點(diǎn)算法就會(huì)繼續(xù)搜索不可能產(chǎn)生新單詞的路徑性能顯著劣化。這正是解法二與解法三的本質(zhì)差別。5.4 DFS 中 Trie 指針推進(jìn)順序錯(cuò)誤先檢查子節(jié)點(diǎn)是否存在再移動(dòng)指針直接node node.children[char]再判空在哈希表版本會(huì)拋空指針/鍵不存在異常Go 版本返回 nil 解引用也會(huì) panic先更新指針再檢查isWord若在更新node之前就檢查isWord會(huì)漏掉當(dāng)前格子構(gòu)成的單詞。5.5 visited 集合與 Trie 配合不當(dāng)使用獨(dú)立 visited 集合時(shí)若每個(gè)新起點(diǎn)沒(méi)有正確初始化或回溯清除visited 狀態(tài)會(huì)阻塞合法路徑。正確做法是每次 DFS 進(jìn)入時(shí)visit.add、退出時(shí)visit.remove保證每條搜索路徑擁有自己的訪問(wèn)歷史。Go 版本用visit[r*COLSc]的一維鍵編碼、Java 版本用r - c字符串鍵本質(zhì)相同。6. 倉(cāng)庫(kù)源碼索引9 種語(yǔ)言的實(shí)現(xiàn)對(duì)照本倉(cāng)庫(kù)在 README 完成度表格README.md中登記了該題的多語(yǔ)言實(shí)現(xiàn)以下是各語(yǔ)言文件的相對(duì)路徑可與本文三種解法一一對(duì)照語(yǔ)言文件路徑實(shí)現(xiàn)要點(diǎn)Pythonpython/0212-word-search-ii.pychildren字典 refsremoveWordDFS 中以refs 1剪枝Javajava/0212-word-search-ii.java內(nèi)嵌Trie類refsremoveWordHashSet去重Ccpp/0212-word-search-ii.cppchildren[26]定長(zhǎng)數(shù)組 isWord原地#標(biāo)記找到后isWord falseGogo/0212-word-search-ii.gorefsremoveWordvisit[r*COLSc]一維訪問(wèn)標(biāo)記JavaScriptjavascript/0212-word-search-ii.js面向?qū)ο蠓庋bTrie節(jié)點(diǎn)存完整word字符串找到后置空TypeScripttypescript/0212-word-search-ii.ts節(jié)點(diǎn)存word布爾標(biāo)記.作為原地訪問(wèn)標(biāo)記Cc/0212-word-search-ii.c手寫TrieNodeparent指針用count計(jì)數(shù)、valid標(biāo)記存活分支Kotlin / Swift / Rustkotlin/0212-word-search-ii.kt、swift/0212-word-search-ii.swift、rust/0212-word-search-ii.rs與解法三結(jié)構(gòu)一致Rust 用OptionBoxTrieNode表達(dá)可斷開(kāi)的子節(jié)點(diǎn)其中 C 語(yǔ)言版本c/0212-word-search-ii.c值得特別關(guān)注它用parent指針在找到單詞后自底向上遍歷整條路徑遞減countcount 0的節(jié)點(diǎn)被置為valid false實(shí)現(xiàn)了與refs等價(jià)的引用計(jì)數(shù)剪枝——這印證了文檔解法三引用計(jì)數(shù) 死分支標(biāo)記思想在不同語(yǔ)言下的通用性。7. 總結(jié)LeetCode 212「Word Search II」是一道經(jīng)典的網(wǎng)格 字典組合題其解題脈絡(luò)清晰遞進(jìn)樸素回溯直觀但低效逐詞獨(dú)立搜索適合作為熱身理解Trie 哈希集合用前綴樹(shù)共享搜索消滅重復(fù)前綴工作但缺少剪枝Trie refs 剪枝用引用計(jì)數(shù)把已找到的單詞從 Trie 中物理移除死分支被切斷是實(shí)戰(zhàn)與面試中的最優(yōu)解。掌握這道題的三個(gè)層次你就同時(shí)掌握了回溯的標(biāo)記—遞歸—復(fù)原三板斧、Trie 的構(gòu)建與遍歷以及計(jì)數(shù)驅(qū)動(dòng)的剪枝這一可遷移到其他字符串/網(wǎng)格組合題如 search-for-word.md、word-search-ii 同源變體的核心技巧。對(duì)照本倉(cāng)庫(kù) 9 種語(yǔ)言的實(shí)現(xiàn)逐一閱讀還能順帶提升多語(yǔ)言視角下的數(shù)據(jù)結(jié)構(gòu)建模能力?！久赓M(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode 212 單詞搜索 II 深度解析：從樸素回溯到 Trie 剪枝的三種解法（leetcode1/leetcode 項(xiàng)目實(shí)戰(zhàn)）
LeetCode 212 單詞搜索 II 深度解析從樸素回溯到 Trie 剪枝的三種解法leetcode1/leetcode 項(xiàng)目實(shí)戰(zhàn)【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode1/leetcode 倉(cāng)庫(kù)中的 search-for-word-ii.md 文檔展開(kāi)完整講解 LeetCode 212「Word Search II」的三種遞進(jìn)式解法樸素回溯Backtracking、Trie 哈希集合、Trie 引用計(jì)數(shù)剪枝并結(jié)合倉(cāng)庫(kù)內(nèi) python/0212-word-search-ii.py、java/0212-word-search-ii.java、cpp/0212-word-search-ii.cpp 等 9 種語(yǔ)言源碼印證實(shí)現(xiàn)細(xì)節(jié)。讀完本文你將掌握二維網(wǎng)格 單詞集合類問(wèn)題的標(biāo)準(zhǔn)套路如何用 DFS 在網(wǎng)格中枚舉路徑、如何用 Trie 共享前綴搜索、以及如何用refs引用計(jì)數(shù)剪枝把性能推到極致。前置知識(shí)Prerequisites在動(dòng)手解這道題之前需要先熟悉四個(gè)基礎(chǔ)概念概念說(shuō)明Backtracking回溯通過(guò)做出選擇、遞歸探索、撤銷選擇來(lái)嘗試所有可能的路徑是窮舉 復(fù)原的經(jīng)典范式DFS深度優(yōu)先搜索沿每條分支盡可能深入后再回溯用于遍歷圖或網(wǎng)格Trie前綴樹(shù)一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)用于高效的前綴匹配與單詞存儲(chǔ)讓多個(gè)單詞共享公共前綴2D Grid Traversal二維網(wǎng)格遍歷在矩陣中沿上下左右四個(gè)方向移動(dòng)同時(shí)處理越界邊界這些概念在倉(cāng)庫(kù)中都有對(duì)應(yīng)實(shí)現(xiàn)例如 implement-prefix-tree.md前綴樹(shù)專題、search-for-word.md單詞搜索版 Word Search I可作為遞進(jìn)閱讀材料。而本倉(cāng)庫(kù)的 README.md 中 0212 一行的完成狀態(tài)表顯示該題在 C/C/C#/Go/Java/JavaScript/Kotlin/Python/Swift/TypeScript 等語(yǔ)言下均有通過(guò)實(shí)現(xiàn)。1. 解法一樸素回溯逐詞搜索1.1 核心直覺(jué)對(duì)words中的每一個(gè)單詞嘗試在棋盤上描出它從匹配首字母的格子出發(fā)沿著上下左右相鄰格子一步步走。為了不讓同一個(gè)格子在一段單詞路徑中被重復(fù)使用臨時(shí)把格子標(biāo)記為已訪問(wèn)探索完成后再恢復(fù)——這正是經(jīng)典回溯。如果某個(gè)單詞的所有字符都能按順序匹配上該單詞就找到了加入結(jié)果集。1.2 算法步驟設(shè)ROWS、COLS為棋盤尺寸對(duì)words中每個(gè)word把每個(gè)格子(r, c)作為潛在起點(diǎn)僅當(dāng)它匹配word[0]運(yùn)行回溯函數(shù)backtrack(r, c, i)i 當(dāng)前需要匹配的word下標(biāo)基線條件i len(word)返回true整個(gè)單詞已匹配若越界或棋盤格子不等于word[i]返回false將格子標(biāo)記為已訪問(wèn)例如替換為*向 4 個(gè)鄰居遞歸下標(biāo)推進(jìn)到i 1恢復(fù)原字符撤銷選擇返回是否存在某個(gè)鄰居路徑成功若任一起點(diǎn)成功把word加入答案并停止搜索該詞。1.3 代碼實(shí)現(xiàn)以下給出 Python / Java / C 三種代表實(shí)現(xiàn)倉(cāng)庫(kù)中 Go / Kotlin / Swift / Rust 版本可在本文末尾源碼索引中找到class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: ROWS, COLS len(board), len(board[0]) res [] def backtrack(r, c, i): if i len(word): return True if (r 0 or c 0 or r ROWS or c COLS or board[r][c] ! word[i] ): return False board[r][c] * ret (backtrack(r 1, c, i 1) or backtrack(r - 1, c, i 1) or backtrack(r, c 1, i 1) or backtrack(r, c - 1, i 1)) board[r][c] word[i] return ret for word in words: flag False for r in range(ROWS): if flag: break for c in range(COLS): if board[r][c] ! word[0]: continue if backtrack(r, c, 0): res.append(word) flag True break return respublic class Solution { public ListString findWords(char[][] board, String[] words) { int ROWS board.length, COLS board[0].length; ListString res new ArrayList(); for (String word : words) { boolean flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word.charAt(0)) continue; if (backtrack(board, r, c, word, 0)) { res.add(word); flag true; break; } } } } return res; } private boolean backtrack(char[][] board, int r, int c, String word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.length || c board[0].length || board[r][c] ! word.charAt(i)) return false; board[r][c] *; boolean ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word.charAt(i); return ret; } }class Solution { public: vectorstring findWords(vectorvectorchar board, vectorstring words) { int ROWS board.size(), COLS board[0].size(); vectorstring res; for (string word : words) { bool flag false; for (int r 0; r ROWS !flag; r) { for (int c 0; c COLS; c) { if (board[r][c] ! word[0]) continue; if (backtrack(board, r, c, word, 0)) { res.push_back(word); flag true; break; } } } } return res; } private: bool backtrack(vectorvectorchar board, int r, int c, string word, int i) { if (i word.length()) return true; if (r 0 || c 0 || r board.size() || c board[0].size() || board[r][c] ! word[i]) return false; board[r][c] *; bool ret backtrack(board, r 1, c, word, i 1) || backtrack(board, r - 1, c, word, i 1) || backtrack(board, r, c 1, word, i 1) || backtrack(board, r, c - 1, word, i 1); board[r][c] word[i]; return ret; } };1.4 復(fù)雜度分析時(shí)間復(fù)雜度$O(w \times m \times n \times 4 \times 3^{t-1})$空間復(fù)雜度$O(t)$其中 $w$ 是單詞個(gè)數(shù)$m$ 是行數(shù)$n$ 是列數(shù)$t$ 是words中最長(zhǎng)單詞的長(zhǎng)度。為什么是 $4 \times 3^{t-1}$每次從當(dāng)前格子出發(fā)第一步有 4 個(gè)方向可選進(jìn)入路徑后由于不能走回頭路當(dāng)前格子已被標(biāo)記后續(xù)每一步最多只有 3 個(gè)有效方向。這種首步 4 選、其后 3 選的結(jié)構(gòu)是網(wǎng)格回溯問(wèn)題復(fù)雜度分析的核心。1.5 局限樸素回溯最大的浪費(fèi)在于w個(gè)單詞完全獨(dú)立搜索彼此之間沒(méi)有任何信息共享。若words [oath, oats, oak]三個(gè)單詞共享前綴oa樸素回溯會(huì)為每個(gè)單詞從零開(kāi)始重新在棋盤上走一遍o - a的前綴路徑重復(fù)勞動(dòng)嚴(yán)重。這正是解法二引入 Trie 的動(dòng)機(jī)。2. 解法二回溯 Trie 哈希集合2.1 核心直覺(jué)逐詞搜索做了大量重復(fù)工作。Trie前綴樹(shù)讓這些工作得以共享在棋盤上行走時(shí)只繼續(xù)那些匹配某個(gè)單詞前綴的路徑。于是棋盤 DFS 探索的是可能的前綴每當(dāng) Trie 節(jié)點(diǎn)表明此前綴是一個(gè)完整單詞時(shí)就記錄下來(lái)。同時(shí)為避免單條路徑中重復(fù)使用同一格子需要在當(dāng)前 DFS 路徑中維護(hù)一個(gè)visited 集合返回時(shí)回溯/移除。2.2 算法步驟用所有words構(gòu)建一棵 Trie每個(gè) Trie 節(jié)點(diǎn)存儲(chǔ)children下一層字母和isWord此處是否為某個(gè)單詞的結(jié)尾初始化res為集合去重visit為當(dāng)前 DFS 路徑的訪問(wèn)集合定義dfs(r, c, node, wordSoFar)若(r, c)越界、已訪問(wèn)、或board[r][c]不在node.children中停止標(biāo)記(r, c)為已訪問(wèn)移動(dòng) Trie 指針node node.children[board[r][c]]把當(dāng)前字符追加到wordSoFar若node.isWord true把wordSoFar加入res用更新后的node和wordSoFar遞歸 4 個(gè)鄰居上下左右回溯把(r, c)從visit中移除從每個(gè)格子(r, c)以 Trie 根節(jié)點(diǎn)為起點(diǎn)運(yùn)行 DFS返回res中收集到的全部單詞。2.3 代碼實(shí)現(xiàn)Pythonclass TrieNode: def __init__(self): self.children {} self.isWord False def addWord(self, word): cur self for c in word: if c not in cur.children: cur.children[c] TrieNode() cur cur.children[c] cur.isWord True class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for w in words: root.addWord(w) ROWS, COLS len(board), len(board[0]) res, visit set(), set() 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 visit.add((r, c)) node node.children[board[r][c]] word board[r][c] if node.isWord: res.add(word) 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)) for r in range(ROWS): for c in range(COLS): dfs(r, c, root, ) return list(res)Java 版本用boolean[][] visit二維數(shù)組代替哈希集合java/0212-word-search-ii.java 中為HashSetString存坐標(biāo)字符串C 版本同樣用vectorvectorboolGo 版本用map[[2]int]bool。三種做法在語(yǔ)義上完全等價(jià)只是去重/標(biāo)記的數(shù)據(jù)結(jié)構(gòu)不同。2.4 復(fù)雜度分析時(shí)間復(fù)雜度$O(m \times n \times 4 \times 3^{t-1} s)$空間復(fù)雜度$O(s)$其中 $m$ 是行數(shù)$n$ 是列數(shù)$t$ 是最長(zhǎng)單詞長(zhǎng)度$s$ 是所有單詞長(zhǎng)度之和即 Trie 的規(guī)模。與解法一相比搜索部分的時(shí)間上界從w倍降為 1 倍所有單詞共享同一趟前綴 DFS但額外付出 $O(s)$ 的空間構(gòu)建 Trie。2.5 兩個(gè)值得注意的細(xì)節(jié)去重結(jié)果集用setPythonset/ JavaHashSet/ Gomap[string]bool因?yàn)槠灞P上可能存在多條路徑拼出同一個(gè)單詞直接 append 會(huì)產(chǎn)生重復(fù)項(xiàng)字符串傳遞word board[r][c]采用不可變字符串逐層傳遞Python/JavaGo 版本同樣用word string(char)而 Rust 版本rust/0212-word-search-ii.rs用word.push(ch) 回溯word.pop()復(fù)用同一可變緩沖區(qū)避免每層拷貝。3. 解法三回溯 Trie引用計(jì)數(shù)剪枝推薦3.1 核心直覺(jué)解法二仍會(huì)在已無(wú)剩余單詞的分支上繼續(xù)探索。解法三在 Trie 上引入激進(jìn)剪枝每個(gè) Trie 節(jié)點(diǎn)維護(hù)refs 字典中還有多少個(gè)單詞經(jīng)過(guò)該節(jié)點(diǎn)成功找到一個(gè)或多個(gè)單詞后每個(gè) DFS 調(diào)用向上返回它在當(dāng)前前綴下新找到的單詞數(shù)量隨著 DFS 回溯從該路徑上的每個(gè) Trie 節(jié)點(diǎn)減去這個(gè)數(shù)量把已找到的單詞從所有相關(guān)節(jié)點(diǎn)移除若某節(jié)點(diǎn)refs減到0說(shuō)明該分支已死亡沒(méi)有剩余單詞用到它直接把父節(jié)點(diǎn)的指針切斷prev.children[...] null讓后續(xù) DFS 永遠(yuǎn)不會(huì)再探索這些無(wú)用的前綴。此外不再使用獨(dú)立的 visited 集合而是原地標(biāo)記棋盤探索某條路徑時(shí)臨時(shí)把board[r][c]設(shè)為*回溯時(shí)恢復(fù)原字符。3.2 Trie 節(jié)點(diǎn)存儲(chǔ)什么每個(gè)節(jié)點(diǎn)包含字段含義children[26]下一層字母定長(zhǎng)數(shù)組比哈希表更快idx若此處是某單詞結(jié)尾記錄其在words中的下標(biāo)否則為-1refs仍存活的、經(jīng)過(guò)該節(jié)點(diǎn)的單詞數(shù)量含在此結(jié)束的單詞3.3 算法步驟構(gòu)建 Trie插入每個(gè)words[i]插入過(guò)程中路徑上的每個(gè)節(jié)點(diǎn)refs加 1結(jié)尾節(jié)點(diǎn)記錄idx i從每個(gè)棋盤格子運(yùn)行dfs(r, c, node)嘗試用board[r][c]擴(kuò)展當(dāng)前 Trie 路徑DFS 規(guī)則若越界、當(dāng)前格子已是*路徑內(nèi)已用、或 Trie 中沒(méi)有board[r][c]對(duì)應(yīng)的子節(jié)點(diǎn)停止否則取字母ch board[r][c]移動(dòng)到子節(jié)點(diǎn)child node.children[ch]標(biāo)記格子board[r][c] *若child.idx ! -1找到單詞把words[child.idx]加入結(jié)果置child.idx -1防重復(fù)初始化found 1向 4 個(gè)鄰居以child遞歸累加返回?cái)?shù)量到found令child.refs - found若child.refs 0切斷該分支node.children[ch] null恢復(fù)棋盤格子返回found使每個(gè)祖先節(jié)點(diǎn)都能更新自己的refs每次頂層 DFS 結(jié)束后root.refs減去返回值返回收集到的結(jié)果。3.4 代碼實(shí)現(xiàn)Pythonclass TrieNode: def __init__(self): self.children [None] * 26 self.idx -1 self.refs 0 def addWord(self, word, i): cur self cur.refs 1 for c in word: index ord(c) - ord(a) if not cur.children[index]: cur.children[index] TrieNode() cur cur.children[index] cur.refs 1 cur.idx i class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for i in range(len(words)): root.addWord(words[i], i) ROWS, COLS len(board), len(board[0]) res [] def getIndex(c): index ord(c) - ord(a) return index def dfs(r, c, node): if (r 0 or c 0 or r ROWS or c COLS or board[r][c] * or not node.children[getIndex(board[r][c])]): return 0 tmp board[r][c] board[r][c] * prev node node node.children[getIndex(tmp)] found 0 if node.idx ! -1: res.append(words[node.idx]) node.idx -1 found 1 found dfs(r 1, c, node) found dfs(r - 1, c, node) found dfs(r, c 1, c, node) if False else dfs(r, c 1, node) found dfs(r, c - 1, node) board[r][c] tmp node.refs - found if not node.refs: prev.children[getIndex(tmp)] None return found for r in range(ROWS): for c in range(COLS): root.refs - dfs(r, c, root) return res上例中dfs(r, c 1, node)的寫法請(qǐng)以文檔原文為準(zhǔn)原文為dfs(r, c 1, node)。注意原始文檔該解法為children定長(zhǎng)數(shù)組26Java/C/C#/Go/Kotlin/Swift/Rust 版本均遵循c - a映射到數(shù)組下標(biāo)的結(jié)構(gòu)例如 cpp/0212-word-search-ii.cpp 中的children[26]與node-children[board[r][c] - a]。3.5 復(fù)雜度分析時(shí)間復(fù)雜度$O(m \times n \times 4 \times 3^{t-1} s)$空間復(fù)雜度$O(s)$其中 $m$ 是行數(shù)$n$ 是列數(shù)$t$ 是最長(zhǎng)單詞長(zhǎng)度$s$ 是所有單詞長(zhǎng)度之和。雖然理論上界與解法二相同但refs剪枝讓實(shí)際運(yùn)行時(shí)間顯著更優(yōu)一旦某分支剩余單詞數(shù)為 0物理切斷指針后后續(xù)所有從其他起點(diǎn)發(fā)起的 DFS 都直接跳過(guò)該分支避免了對(duì)死前綴的重復(fù)探索。4. 三種解法對(duì)比總覽維度解法一樸素回溯解法二Trie 哈希集合解法三Trie refs 剪枝是否共享前綴否逐詞獨(dú)立是是訪問(wèn)標(biāo)記原地*獨(dú)立 visited 集合原地*去重方式逐詞只加一次結(jié)果集合setidx -1剪枝策略無(wú)無(wú)僅前綴匹配refs計(jì)數(shù) 斷鏈時(shí)間上界$O(w \cdot m \cdot n \cdot 4 \cdot 3^{t-1})$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$$O(m \cdot n \cdot 4 \cdot 3^{t-1} s)$空間上界$O(t)$$O(s)$$O(s)$實(shí)戰(zhàn)性能最差重復(fù)前綴搜索中等最優(yōu)死分支被物理剪除解法三既是面試中的加分答案也是倉(cāng)庫(kù)中各語(yǔ)言實(shí)現(xiàn)的主流形態(tài)。5. 常見(jiàn)陷阱與規(guī)避Common Pitfalls5.1 忘記對(duì)結(jié)果去重棋盤上多條路徑可能拼出同一個(gè)單詞直接加入結(jié)果列表會(huì)產(chǎn)生重復(fù)項(xiàng)。規(guī)避方式有兩種結(jié)果用集合set存儲(chǔ)在 Trie 中標(biāo)記單詞已被找到把結(jié)尾節(jié)點(diǎn)的idx置為-1解法三或把isWord/word置空解法二變體。例如倉(cāng)庫(kù) javascript/0212-word-search-ii.js 中checkWord找到單詞后執(zhí)行node.word 正是標(biāo)記已找到的寫法python/0212-word-search-ii.py 則同時(shí)用node.isWord False與res集合雙重保險(xiǎn)。5.2 回溯后沒(méi)有恢復(fù)棋盤直接在棋盤上標(biāo)記如board[r][c] *后若遞歸結(jié)束忘記恢復(fù)原字符棋盤狀態(tài)被破壞其他起點(diǎn)或其他單詞將無(wú)法找到有效路徑。正確做法是保存tmp board[r][c]在遞歸返回后恢復(fù)。5.3 構(gòu)建了 Trie 卻不剪枝建好 Trie 但找到單詞后不剪枝會(huì)導(dǎo)致持續(xù)探索死分支沒(méi)有遞減refs、沒(méi)有在refs歸零時(shí)刪除節(jié)點(diǎn)算法就會(huì)繼續(xù)搜索不可能產(chǎn)生新單詞的路徑性能顯著劣化。這正是解法二與解法三的本質(zhì)差別。5.4 DFS 中 Trie 指針推進(jìn)順序錯(cuò)誤先檢查子節(jié)點(diǎn)是否存在再移動(dòng)指針直接node node.children[char]再判空在哈希表版本會(huì)拋空指針/鍵不存在異常Go 版本返回 nil 解引用也會(huì) panic先更新指針再檢查isWord若在更新node之前就檢查isWord會(huì)漏掉當(dāng)前格子構(gòu)成的單詞。5.5 visited 集合與 Trie 配合不當(dāng)使用獨(dú)立 visited 集合時(shí)若每個(gè)新起點(diǎn)沒(méi)有正確初始化或回溯清除visited 狀態(tài)會(huì)阻塞合法路徑。正確做法是每次 DFS 進(jìn)入時(shí)visit.add、退出時(shí)visit.remove保證每條搜索路徑擁有自己的訪問(wèn)歷史。Go 版本用visit[r*COLSc]的一維鍵編碼、Java 版本用r - c字符串鍵本質(zhì)相同。6. 倉(cāng)庫(kù)源碼索引9 種語(yǔ)言的實(shí)現(xiàn)對(duì)照本倉(cāng)庫(kù)在 README 完成度表格README.md中登記了該題的多語(yǔ)言實(shí)現(xiàn)以下是各語(yǔ)言文件的相對(duì)路徑可與本文三種解法一一對(duì)照語(yǔ)言文件路徑實(shí)現(xiàn)要點(diǎn)Pythonpython/0212-word-search-ii.pychildren字典 refsremoveWordDFS 中以refs 1剪枝Javajava/0212-word-search-ii.java內(nèi)嵌Trie類refsremoveWordHashSet去重Ccpp/0212-word-search-ii.cppchildren[26]定長(zhǎng)數(shù)組 isWord原地#標(biāo)記找到后isWord falseGogo/0212-word-search-ii.gorefsremoveWordvisit[r*COLSc]一維訪問(wèn)標(biāo)記JavaScriptjavascript/0212-word-search-ii.js面向?qū)ο蠓庋bTrie節(jié)點(diǎn)存完整word字符串找到后置空TypeScripttypescript/0212-word-search-ii.ts節(jié)點(diǎn)存word布爾標(biāo)記.作為原地訪問(wèn)標(biāo)記Cc/0212-word-search-ii.c手寫TrieNodeparent指針用count計(jì)數(shù)、valid標(biāo)記存活分支Kotlin / Swift / Rustkotlin/0212-word-search-ii.kt、swift/0212-word-search-ii.swift、rust/0212-word-search-ii.rs與解法三結(jié)構(gòu)一致Rust 用OptionBoxTrieNode表達(dá)可斷開(kāi)的子節(jié)點(diǎn)其中 C 語(yǔ)言版本c/0212-word-search-ii.c值得特別關(guān)注它用parent指針在找到單詞后自底向上遍歷整條路徑遞減countcount 0的節(jié)點(diǎn)被置為valid false實(shí)現(xiàn)了與refs等價(jià)的引用計(jì)數(shù)剪枝——這印證了文檔解法三引用計(jì)數(shù) 死分支標(biāo)記思想在不同語(yǔ)言下的通用性。7. 總結(jié)LeetCode 212「Word Search II」是一道經(jīng)典的網(wǎng)格 字典組合題其解題脈絡(luò)清晰遞進(jìn)樸素回溯直觀但低效逐詞獨(dú)立搜索適合作為熱身理解Trie 哈希集合用前綴樹(shù)共享搜索消滅重復(fù)前綴工作但缺少剪枝Trie refs 剪枝用引用計(jì)數(shù)把已找到的單詞從 Trie 中物理移除死分支被切斷是實(shí)戰(zhàn)與面試中的最優(yōu)解。掌握這道題的三個(gè)層次你就同時(shí)掌握了回溯的標(biāo)記—遞歸—復(fù)原三板斧、Trie 的構(gòu)建與遍歷以及計(jì)數(shù)驅(qū)動(dòng)的剪枝這一可遷移到其他字符串/網(wǎng)格組合題如 search-for-word.md、word-search-ii 同源變體的核心技巧。對(duì)照本倉(cāng)庫(kù) 9 種語(yǔ)言的實(shí)現(xiàn)逐一閱讀還能順帶提升多語(yǔ)言視角下的數(shù)據(jù)結(jié)構(gòu)建模能力?！久赓M(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考