化)
LeetCode-Go 題解212. Word Search II —— 從樸素 DFS 到 Trie 前綴樹優(yōu)化【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導(dǎo)讀本文以 LeetCode 212Word Search II為核心講解如何在二維字符網(wǎng)格中同時查找字典中的多個單詞。題目本身是 79. Word Search 的加強版本倉庫給出了基于 79 題exist函數(shù)逐詞 DFS 的樸素實現(xiàn)見 leetcode/0212.Word-Search-II/212. Word Search II.go并以測試用例驗證了正確性。讀完本文你將掌握題目約束與復(fù)雜度分析、倉庫內(nèi)樸素實現(xiàn)的逐行拆解、以及如何借助前綴樹Trie參見 leetcode/0208.Implement-Trie-Prefix-Tree.go) 的實現(xiàn)模式把多個單詞的搜索合并為一次共享前綴的深度優(yōu)先遍歷大幅降低時間復(fù)雜度。題目描述與約束給定一個二維字符網(wǎng)格board和一個字典單詞列表words找出所有同時出現(xiàn)在二維網(wǎng)格和字典中的單詞。單詞必須按照字母順序由水平相鄰或垂直相鄰的單元格中的字母依次構(gòu)成同一個單元格內(nèi)的字母在一個單詞中不允許被重復(fù)使用即一個單詞的搜索路徑不能自交。示例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]約束條件所有輸入只包含小寫字母a-zwords中的單詞互不重復(fù)。題目大意在一個m × n的網(wǎng)格與一個字典之間求交集網(wǎng)格中可以按相鄰關(guān)系拼出來的單詞且該單詞同時出現(xiàn)在words列表中就輸出它。示例中oath與eat都能在網(wǎng)格中拼出且出現(xiàn)在字典里而pea、rain無法在網(wǎng)格中完整拼出故被排除。解題思路基于 79 題的樸素 DFS為什么說它是 79 題的加強版Word Search 只判斷單個單詞是否存在于網(wǎng)格中而 212 題把輸入從單個字符串?dāng)U展成字符串?dāng)?shù)組words要求一次性返回所有能被拼出的單詞。倉庫文檔在 212. Word Search II 題解 中明確指出思路仍然可以照搬 79 題的 DFS 搜索但時間復(fù)雜度特別高——若words共有k個單詞每個單詞都獨立地在整個網(wǎng)格上跑一遍 DFS總開銷約為k倍的單次搜索開銷網(wǎng)格大、單詞多時會非常昂貴。因此文檔以想想更優(yōu)的解法收尾指向下文的前綴樹優(yōu)化。倉庫內(nèi)樸素實現(xiàn)的完整拆解本倉庫在 212. Word Search II.go 中給出了逐詞復(fù)用 79 題exist的實現(xiàn)代碼結(jié)構(gòu)如下func findWords(board [][]byte, words []string) []string { res : []string{} for _, v : range words { if exist(board, v) { res append(res, v) } } return res }findWords對字典中的每個單詞依次調(diào)用exist命中就追加到結(jié)果切片res。由于words值互異題目 Note 保證結(jié)果天然不會重復(fù)。// these is 79 solution var dir [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, }dir定義四個搜索方向上、右、下、左。每個方向的偏移量恰好對應(yīng)網(wǎng)格坐標(biāo)系中(x, y)的四個鄰居。func exist(board [][]byte, word string) bool { visited : make([][]bool, len(board)) for i : 0; i len(visited); i { visited[i] make([]bool, len(board[0])) } for i, v : range board { for j : range v { if searchWord(board, visited, word, 0, i, j) { return true } } } return false }exist負(fù)責(zé)兩件事一是初始化與網(wǎng)格同尺寸的visited布爾矩陣標(biāo)記當(dāng)前單詞的搜索路徑上哪些格子已被占用從而滿足同一個字母單元格在一個單詞中不允許重復(fù)使用的約束二是以網(wǎng)格中每個格子為起點調(diào)用searchWord只要任一位置能拼出完整單詞就返回true。func isInBoard(board [][]byte, x, y int) bool { return x 0 x len(board) y 0 y len(board[0]) } func searchWord(board [][]byte, visited [][]bool, word string, index, x, y int) bool { if index len(word)-1 { return board[x][y] word[index] } if board[x][y] word[index] { visited[x][y] true for i : 0; i 4; i { nx : x dir[i][0] ny : y dir[i][1] if isInBoard(board, nx, ny) !visited[nx][ny] searchWord(board, visited, word, index1, nx, ny) { return true } } visited[x][y] false } return false }searchWord是核心回溯函數(shù)終止條件當(dāng)index len(word)-1時只需判斷當(dāng)前格子字母是否等于單詞最后一個字母匹配分支若當(dāng)前格子字母與word[index]相等先置visited[x][y] true防止本路徑回頭再向四個方向遞歸尋找index1回溯還原四個方向都失敗時執(zhí)行visited[x][y] false把格子釋放給其他起點或方向使用越界與占用檢查遞歸前用isInBoard保證坐標(biāo)合法用!visited[nx][ny]保證不重復(fù)使用格子。樸素實現(xiàn)的復(fù)雜度設(shè)網(wǎng)格為m × n單詞平均長度為L單詞個數(shù)為k時間復(fù)雜度約O(k · m · n · 4^L)。每個單詞都要獨立從所有格子出發(fā)做回溯搜索分支因子最大為 4空間復(fù)雜度O(m · n)visited矩陣加上遞歸棧深度O(L)。這就是文檔強調(diào)時間復(fù)雜度特別高的原因k個單詞存在大量共享前綴樸素實現(xiàn)卻把相同前綴的探索重復(fù)執(zhí)行了k次。測試用例驗證倉庫在 212. Word Search II_test.go 中覆蓋了兩個場景79 題經(jīng)典網(wǎng)格[[A,B,C,E],[S,F,C,S],[A,D,E,E]]配合[ABCCED,SEE,ABCB]期望輸出[ABCCED,SEE]——驗證了ABCB雖然能部分拼出但最終無法走通證明回溯邏輯正確本題示例網(wǎng)格[[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]]配合[oath,pea,eat,rain]期望輸出[oath,eat]。更優(yōu)解法Trie 深度優(yōu)先搜索文檔末尾提示想想更優(yōu)的解法標(biāo)準(zhǔn)答案是用前綴樹Trie合并所有單詞的前綴再在網(wǎng)格上做一次共享的 DFS。本倉庫雖未對 212 單獨實現(xiàn)該方案但提供了可直接參考的 Trie 數(shù)據(jù)結(jié)構(gòu)的 Go 實現(xiàn)見 leetcode/0208.Implement-Trie-Prefix-Tree/208. Implement Trie (Prefix Tree).go.go)type Trie struct { isWord bool children map[rune]*Trie }其核心思想是每個節(jié)點children存儲以該節(jié)點為前綴的下一字符映射isWord標(biāo)記是否存在以該節(jié)點結(jié)尾的完整單詞Insert沿字符逐層建鏈并在終點置isWord true對應(yīng)208題解 208. Implement Trie (Prefix Tree).go.go#L14-L26)Search/StartsWith沿前綴逐層查詢208. Implement Trie (Prefix Tree).go.go#L29-L52)后者正是 DFS 剪枝所需要的該前綴是否還有單詞可拼判斷。Trie 化的解題流程用words中所有單詞構(gòu)建一棵 Trie從網(wǎng)格中每個格子出發(fā)做 DFS同時維護當(dāng)前節(jié)點在 Trie 中的位置剪枝若當(dāng)前 Trie 節(jié)點下不存在任何單詞以當(dāng)前路徑為前綴等價于StartsWith失敗立即終止該路徑不再繼續(xù)四方向探索收集結(jié)果當(dāng) DFS 到達某個isWord true的節(jié)點時記錄該單詞并將該節(jié)點的isWord置為false防止重復(fù)輸出沿用 79 題的visited回溯機制保證一個單詞的路徑不重復(fù)使用格子。為什么 Trie 方案更快樸素實現(xiàn)中[oath,oats,oak]這類共享oa前綴的單詞會在網(wǎng)格上重復(fù)搜索oa三次Trie 方案把前綴合并為一棵字典樹一次 DFS 同時覆蓋所有以該前綴開頭的單詞只有當(dāng)路徑前綴在 Trie 中無后繼時才剪枝。整體復(fù)雜度從O(k · m · n · 4^L)降為約O(m · n · 4^L)L為最長匹配路徑長度空間上以 Trie 的存儲換取搜索次數(shù)的減少。與 208 題 Trie 的銜接要點若基于本倉庫的 Trie 實現(xiàn)改造需要注意兩點其一208的 Trie 用map[rune]*Trie存儲子節(jié)點DFS 中可通過children[rune(board[x][y])]在O(1)時間內(nèi)判斷下一格字母是否是合法后繼其二DFS 遞歸參數(shù)需要同時攜帶當(dāng)前 Trie 節(jié)點指針與當(dāng)前拼出的字符串或在節(jié)點上記錄單詞到達isWord節(jié)點時即可輸出。實際應(yīng)用中還可將網(wǎng)格改為原地標(biāo)記如把已訪問格子字符臨時改為#以省去visited矩陣屬于實現(xiàn)層面的進一步優(yōu)化。小結(jié)樸素實現(xiàn)復(fù)用 79. Word Search 的exist逐詞 DFS正確但時間復(fù)雜度高適合理解回溯本質(zhì)進階思路用 Trie 合并words前綴、DFS 共享搜索并剪枝是本題的工業(yè)級解法也是文檔想想更優(yōu)的解法指向的方向倉庫證據(jù)鏈完整實現(xiàn)見 212. Word Search II.go測試見 212. Word Search II_test.goTrie 參考實現(xiàn)見 208. Implement Trie (Prefix Tree).go.go)。從一個單詞79到一批單詞212再到前綴合并共享搜索這條演化路徑既是面試高頻考點也是把回溯、剪枝與字典樹三類基本功融會貫通的絕佳練習(xí)。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode-Go 題解：212. Word Search II —— 從樸素 DFS 到 Trie 前綴樹優(yōu)化
LeetCode-Go 題解212. Word Search II —— 從樸素 DFS 到 Trie 前綴樹優(yōu)化【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導(dǎo)讀本文以 LeetCode 212Word Search II為核心講解如何在二維字符網(wǎng)格中同時查找字典中的多個單詞。題目本身是 79. Word Search 的加強版本倉庫給出了基于 79 題exist函數(shù)逐詞 DFS 的樸素實現(xiàn)見 leetcode/0212.Word-Search-II/212. Word Search II.go并以測試用例驗證了正確性。讀完本文你將掌握題目約束與復(fù)雜度分析、倉庫內(nèi)樸素實現(xiàn)的逐行拆解、以及如何借助前綴樹Trie參見 leetcode/0208.Implement-Trie-Prefix-Tree.go) 的實現(xiàn)模式把多個單詞的搜索合并為一次共享前綴的深度優(yōu)先遍歷大幅降低時間復(fù)雜度。題目描述與約束給定一個二維字符網(wǎng)格board和一個字典單詞列表words找出所有同時出現(xiàn)在二維網(wǎng)格和字典中的單詞。單詞必須按照字母順序由水平相鄰或垂直相鄰的單元格中的字母依次構(gòu)成同一個單元格內(nèi)的字母在一個單詞中不允許被重復(fù)使用即一個單詞的搜索路徑不能自交。示例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]約束條件所有輸入只包含小寫字母a-zwords中的單詞互不重復(fù)。題目大意在一個m × n的網(wǎng)格與一個字典之間求交集網(wǎng)格中可以按相鄰關(guān)系拼出來的單詞且該單詞同時出現(xiàn)在words列表中就輸出它。示例中oath與eat都能在網(wǎng)格中拼出且出現(xiàn)在字典里而pea、rain無法在網(wǎng)格中完整拼出故被排除。解題思路基于 79 題的樸素 DFS為什么說它是 79 題的加強版Word Search 只判斷單個單詞是否存在于網(wǎng)格中而 212 題把輸入從單個字符串?dāng)U展成字符串?dāng)?shù)組words要求一次性返回所有能被拼出的單詞。倉庫文檔在 212. Word Search II 題解 中明確指出思路仍然可以照搬 79 題的 DFS 搜索但時間復(fù)雜度特別高——若words共有k個單詞每個單詞都獨立地在整個網(wǎng)格上跑一遍 DFS總開銷約為k倍的單次搜索開銷網(wǎng)格大、單詞多時會非常昂貴。因此文檔以想想更優(yōu)的解法收尾指向下文的前綴樹優(yōu)化。倉庫內(nèi)樸素實現(xiàn)的完整拆解本倉庫在 212. Word Search II.go 中給出了逐詞復(fù)用 79 題exist的實現(xiàn)代碼結(jié)構(gòu)如下func findWords(board [][]byte, words []string) []string { res : []string{} for _, v : range words { if exist(board, v) { res append(res, v) } } return res }findWords對字典中的每個單詞依次調(diào)用exist命中就追加到結(jié)果切片res。由于words值互異題目 Note 保證結(jié)果天然不會重復(fù)。// these is 79 solution var dir [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, }dir定義四個搜索方向上、右、下、左。每個方向的偏移量恰好對應(yīng)網(wǎng)格坐標(biāo)系中(x, y)的四個鄰居。func exist(board [][]byte, word string) bool { visited : make([][]bool, len(board)) for i : 0; i len(visited); i { visited[i] make([]bool, len(board[0])) } for i, v : range board { for j : range v { if searchWord(board, visited, word, 0, i, j) { return true } } } return false }exist負(fù)責(zé)兩件事一是初始化與網(wǎng)格同尺寸的visited布爾矩陣標(biāo)記當(dāng)前單詞的搜索路徑上哪些格子已被占用從而滿足同一個字母單元格在一個單詞中不允許重復(fù)使用的約束二是以網(wǎng)格中每個格子為起點調(diào)用searchWord只要任一位置能拼出完整單詞就返回true。func isInBoard(board [][]byte, x, y int) bool { return x 0 x len(board) y 0 y len(board[0]) } func searchWord(board [][]byte, visited [][]bool, word string, index, x, y int) bool { if index len(word)-1 { return board[x][y] word[index] } if board[x][y] word[index] { visited[x][y] true for i : 0; i 4; i { nx : x dir[i][0] ny : y dir[i][1] if isInBoard(board, nx, ny) !visited[nx][ny] searchWord(board, visited, word, index1, nx, ny) { return true } } visited[x][y] false } return false }searchWord是核心回溯函數(shù)終止條件當(dāng)index len(word)-1時只需判斷當(dāng)前格子字母是否等于單詞最后一個字母匹配分支若當(dāng)前格子字母與word[index]相等先置visited[x][y] true防止本路徑回頭再向四個方向遞歸尋找index1回溯還原四個方向都失敗時執(zhí)行visited[x][y] false把格子釋放給其他起點或方向使用越界與占用檢查遞歸前用isInBoard保證坐標(biāo)合法用!visited[nx][ny]保證不重復(fù)使用格子。樸素實現(xiàn)的復(fù)雜度設(shè)網(wǎng)格為m × n單詞平均長度為L單詞個數(shù)為k時間復(fù)雜度約O(k · m · n · 4^L)。每個單詞都要獨立從所有格子出發(fā)做回溯搜索分支因子最大為 4空間復(fù)雜度O(m · n)visited矩陣加上遞歸棧深度O(L)。這就是文檔強調(diào)時間復(fù)雜度特別高的原因k個單詞存在大量共享前綴樸素實現(xiàn)卻把相同前綴的探索重復(fù)執(zhí)行了k次。測試用例驗證倉庫在 212. Word Search II_test.go 中覆蓋了兩個場景79 題經(jīng)典網(wǎng)格[[A,B,C,E],[S,F,C,S],[A,D,E,E]]配合[ABCCED,SEE,ABCB]期望輸出[ABCCED,SEE]——驗證了ABCB雖然能部分拼出但最終無法走通證明回溯邏輯正確本題示例網(wǎng)格[[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]]配合[oath,pea,eat,rain]期望輸出[oath,eat]。更優(yōu)解法Trie 深度優(yōu)先搜索文檔末尾提示想想更優(yōu)的解法標(biāo)準(zhǔn)答案是用前綴樹Trie合并所有單詞的前綴再在網(wǎng)格上做一次共享的 DFS。本倉庫雖未對 212 單獨實現(xiàn)該方案但提供了可直接參考的 Trie 數(shù)據(jù)結(jié)構(gòu)的 Go 實現(xiàn)見 leetcode/0208.Implement-Trie-Prefix-Tree/208. Implement Trie (Prefix Tree).go.go)type Trie struct { isWord bool children map[rune]*Trie }其核心思想是每個節(jié)點children存儲以該節(jié)點為前綴的下一字符映射isWord標(biāo)記是否存在以該節(jié)點結(jié)尾的完整單詞Insert沿字符逐層建鏈并在終點置isWord true對應(yīng)208題解 208. Implement Trie (Prefix Tree).go.go#L14-L26)Search/StartsWith沿前綴逐層查詢208. Implement Trie (Prefix Tree).go.go#L29-L52)后者正是 DFS 剪枝所需要的該前綴是否還有單詞可拼判斷。Trie 化的解題流程用words中所有單詞構(gòu)建一棵 Trie從網(wǎng)格中每個格子出發(fā)做 DFS同時維護當(dāng)前節(jié)點在 Trie 中的位置剪枝若當(dāng)前 Trie 節(jié)點下不存在任何單詞以當(dāng)前路徑為前綴等價于StartsWith失敗立即終止該路徑不再繼續(xù)四方向探索收集結(jié)果當(dāng) DFS 到達某個isWord true的節(jié)點時記錄該單詞并將該節(jié)點的isWord置為false防止重復(fù)輸出沿用 79 題的visited回溯機制保證一個單詞的路徑不重復(fù)使用格子。為什么 Trie 方案更快樸素實現(xiàn)中[oath,oats,oak]這類共享oa前綴的單詞會在網(wǎng)格上重復(fù)搜索oa三次Trie 方案把前綴合并為一棵字典樹一次 DFS 同時覆蓋所有以該前綴開頭的單詞只有當(dāng)路徑前綴在 Trie 中無后繼時才剪枝。整體復(fù)雜度從O(k · m · n · 4^L)降為約O(m · n · 4^L)L為最長匹配路徑長度空間上以 Trie 的存儲換取搜索次數(shù)的減少。與 208 題 Trie 的銜接要點若基于本倉庫的 Trie 實現(xiàn)改造需要注意兩點其一208的 Trie 用map[rune]*Trie存儲子節(jié)點DFS 中可通過children[rune(board[x][y])]在O(1)時間內(nèi)判斷下一格字母是否是合法后繼其二DFS 遞歸參數(shù)需要同時攜帶當(dāng)前 Trie 節(jié)點指針與當(dāng)前拼出的字符串或在節(jié)點上記錄單詞到達isWord節(jié)點時即可輸出。實際應(yīng)用中還可將網(wǎng)格改為原地標(biāo)記如把已訪問格子字符臨時改為#以省去visited矩陣屬于實現(xiàn)層面的進一步優(yōu)化。小結(jié)樸素實現(xiàn)復(fù)用 79. Word Search 的exist逐詞 DFS正確但時間復(fù)雜度高適合理解回溯本質(zhì)進階思路用 Trie 合并words前綴、DFS 共享搜索并剪枝是本題的工業(yè)級解法也是文檔想想更優(yōu)的解法指向的方向倉庫證據(jù)鏈完整實現(xiàn)見 212. Word Search II.go測試見 212. Word Search II_test.goTrie 參考實現(xiàn)見 208. Implement Trie (Prefix Tree).go.go)。從一個單詞79到一批單詞212再到前綴合并共享搜索這條演化路徑既是面試高頻考點也是把回溯、剪枝與字典樹三類基本功融會貫通的絕佳練習(xí)。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考