題目描述:給定二維字元網格和一個單詞,判斷單詞是否存在於網格中(可水平或垂直相鄰,每個格子只能用一次)。
解題思路:DFS + 回溯。從每個與單詞首字元匹配的格子開始,遞迴向四個方向延伸。為避免重複使用同一格子,每次進入時暫時修改格子值(如設為 '#'),回溯時恢復原值。若找到完整單詞回傳 true。
時間複雜度:O(m × n × 4^L),L 為單詞長度 — 最壞情況下從每格嘗試所有路徑。
空間複雜度:O(L) — 遞迴棧深度等於單詞長度。
1. For each cell (i, j) matching word[0]:
a. DFS(i, j, k=0):
- If k == word.length: return true
- If out of bounds or mismatch: return false
- Mark cell as visited
- Recurse in 4 directions with k+1
- Unmark (backtrack)
2. Return false if no path foundBFS O(m×n×4^L) 最壞情況:用隊列代替遞迴 DFS — 同複雜度但空間用於隊列而非堆疊。
Trie 預處理:若多次搜尋,先建 Trie 可加速 — 但單次搜尋無益。