給定一個 m x n 的字元網格
board和一個字串word，判斷 word 是否存在於網格中。單字可以由相鄰（水平或垂直）的格子中的字母構成，同一格不能重複使用。
Example:
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true
Intuition
TIP
核心思路：從每個格子出發，用 DFS + 回溯嘗試匹配 word 的每個字元，走過的格子標記避免重複使用。
- 每個格子都可能是起點，嘗試所有起點
- 從起點出發，往四個方向 DFS，每步匹配 word 的下一個字元
- 回溯：走過的格子要標記（避免重複使用），回來時恢復
Approaches
1. DFS + Extra visited Array — O(m * n * 4^L) / O(m * n)
- Idea: 用一個 boolean 矩陣記錄已走過的格子
- Time:
O(m * n * 4^L)- L 為 word 長度 - Space:
O(m * n)- visited 陣列 + 遞迴深度
class Solution {
fun exist(board: Array<CharArray>, word: String): Boolean {
val m = board.size
val n = board[0].size
val visited = Array(m) { BooleanArray(n) }
fun dfs(i: Int, j: Int, k: Int): Boolean {
if (k == word.length) return true
if (i < 0 || i >= m || j < 0 || j >= n) return false
if (visited[i][j] || board[i][j] != word[k]) return false
visited[i][j] = true
val found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1)
visited[i][j] = false
return found
}
for (i in 0 until m) {
for (j in 0 until n) {
if (dfs(i, j, 0)) return true
}
}
return false
}
}⭐ 2. DFS + In-place Marking (space-optimal) — O(m * n * 4^L) / O(L)
- Idea: 不使用額外 visited 陣列，直接將走過的格子改為特殊字元（如 ’#’），回溯時恢復原值
- Time:
O(m * n * 4^L) - Space:
O(L)- 僅遞迴深度
class Solution {
fun exist(board: Array<CharArray>, word: String): Boolean {
val m = board.size
val n = board[0].size
fun dfs(i: Int, j: Int, k: Int): Boolean {
if (k == word.length) return true
if (i < 0 || i >= m || j < 0 || j >= n) return false
if (board[i][j] != word[k]) return false
val temp = board[i][j]
board[i][j] = '#' // 標記已走過
val found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1)
board[i][j] = temp // 回溯恢復
return found
}
for (i in 0 until m) {
for (j in 0 until n) {
if (dfs(i, j, 0)) return true
}
}
return false
}
}WARNING
原地修改 board 在多執行緒環境下不安全。面試時可以提到這個 trade-off：省空間 vs 安全性。
🔑 Takeaways
- Pattern: 網格 DFS + 回溯是矩陣搜尋問題的標準模板
- Key trick: 原地標記（改成特殊字元再恢復）省去 visited 陣列；提前判斷不匹配可以大幅剪枝