LeetCode 79 - Word Search 解題筆記

🏷️ 題目基本資訊

• 題目名稱： Word Search
• 題號編號： 79
• 難度：Medium
• 題目分類： Backtrack
• 連結：LeetCode 題目連結

🧠 題目目標

給定一個 m x n 的字母矩陣 board 和一個字串 word，判斷 word 是否存在於矩陣中。

• 單字可以從任一格開始搜尋
• 每步只能向上下左右移動到相鄰的格子
• 每個格子只能用一次

🔍 解題邏輯與步驟

1. 逐格嘗試：對每個 cell 嘗試是否可以從這裡開始找 word。
2. 深度優先搜尋（DFS）：一旦找到起點就向四周延伸比對字串。
3. 邊界與狀態判斷：
   • 越界直接回傳 false
   • 若字母不符合當前字元，回傳 false
4. 記錄已訪位置：將走過的格子暫時設為 '#'，防止重複走訪。
5. 成功條件：當 index === word.length，代表整個字串已比對完成。
6. 回溯（backtracking）：走錯時要還原格子內容，讓其他路徑可用。

---

💡 程式邏輯簡略圖（Pseudocode）

exist(board, word):
    for each cell (i, j) in board:
        if board[i][j] === word[0]:
            if dfs(i, j, 0):
                return true
    return false

dfs(i, j, index):
    if index === word.length:
        return true

    if i < 0 or i >= rows or j < 0 or j >= cols:
        return false
    if board[i][j] !== word[index]:
        return false

    temp = board[i][j]
    board[i][j] = '#'  // 標記走過

    for each (dx, dy) in [[-1,0],[1,0],[0,-1],[0,1]]:
        if dfs(i+dx, j+dy, index+1):
            return true

    board[i][j] = temp  // 回溯
    return false

✨ 重點技巧

使用 DFS 遞迴逐步檢查字母是否匹配

每次遞迴都傳入 index + 1，表示比對下一個字元

回溯還原（board[i][j] = temp）是 DFS 成敗與否的關鍵

以 # 作為標記代表此格已被使用

時間與空間複雜度分析

時間複雜度：最壞情況為 O(m _ n _ 3^L)
（m × n 為起點總數，L 為 word.length，每格最多往 3 個方向擴展）

空間複雜度：O(L) 為遞迴深度