題目描述:在二維字元網格中,找出字典中所有能在網格裡找到的單詞。
解題思路:Trie + DFS 回溯。先將所有單詞建成 Trie。然後從每個網格格子出發做 DFS,沿著 Trie 節點走。若走到的 Trie 節點有 isEnd 標記,記錄此單詞。Trie 讓我們提早剪枝(若當前前綴不在 Trie 中,無需繼續);找到後將節點的 isEnd 清除,避免重複添加相同單詞。
時間複雜度:O(M × N × 4^L),M×N 為網格大小,L 為最長單詞長度 — Trie 剪枝大幅減少實際搜尋量。
空間複雜度:O(W × L),W 為單詞數,L 為平均長度 — Trie 空間。
1. Build Trie from word list
2. For each cell (r, c) in board:
a. DFS(r, c, trieRoot):
- If out of bounds or char not in Trie: return
- If Trie node has word: add to result, clear to avoid duplicates
- Mark cell visited, recurse 4 directions, unmark
3. Return result逐詞 DFS O(n×m×n×4^L) 最壞:對每個單詞呼叫 word search — 時間複雜度極差。
雜湊表前綴檢查 O(nm×4^L×|word|) 平均:檢查每個生成的路徑,查詢雜湊表 — 時間複雜度未必更優。