LeetCode 筆記：單詞搜索 - DFS 回溯在矩陣中查找路徑

問題描述

給定 m x n 字符矩陣 board 和字符串 word，判斷 word 是否能由矩陣中相鄰單元格（上下左右）順序構成。同一單元格不可重複使用。

範例：

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]]
word = "ABCCED" → true
word = "SEE"    → true
word = "ABCB"   → false

解題思路：DFS + 回溯

從每個單元格作為起點嘗試 DFS：

1. 邊界檢查：越界返回 false
2. 字符匹配：不匹配返回 false
3. 訪問標記：用 visited 數組防止重複使用
4. 四方向遞歸：任一方向成功即返回 true
5. 回溯恢復：撤銷訪問標記

C++ 完整實現

class Solution {
public:
    bool exist(vector>& board, string word) {
        int m = board.size(), n = board[0].size();
        vector> visited(m, vector(n, false));
        
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (dfs(board, visited, word, 0, i, j))
                    return true;
        return false;
    }
    
private:
    bool dfs(vector>& board, vector>& visited,
             const string& word, int idx, int x, int y) {
        if (idx == word.size()) return true;  // 完全匹配
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) return false;
        if (visited[x][y]) return false;
        if (board[x][y] != word[idx]) return false;
        
        visited[x][y] = true;
        bool found = dfs(board, visited, word, idx+1, x+1, y) ||
                     dfs(board, visited, word, idx+1, x-1, y) ||
                     dfs(board, visited, word, idx+1, x, y+1) ||
                     dfs(board, visited, word, idx+1, x, y-1);
        visited[x][y] = false;  // 回溯
        return found;
    }
};

空間優化：原地修改 board 標記

不額外分配 visited，直接修改 board[x][y] 為特殊字符（如 '#'），回溯時恢復。

bool dfs(vector>& board, const string& word, int idx, int x, int y) {
    if (idx == word.size()) return true;
    if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) return false;
    if (board[x][y] != word[idx]) return false;
    
    char tmp = board[x][y];
    board[x][y] = '#';  // 標記已訪問
    bool found = dfs(board, word, idx+1, x+1, y) ||
                 dfs(board, word, idx+1, x-1, y) ||
                 dfs(board, word, idx+1, x, y+1) ||
                 dfs(board, word, idx+1, x, y-1);
    board[x][y] = tmp;  // 恢復
    return found;
}

複雜度分析

關鍵剪枝優化

1. 字符頻率預檢：統計 board 中各字符數量，若 word 需求超過直接返回 false
2. 反轉優化：若 word 尾部字符較稀有，反轉 word 再搜索（減少失敗分支）
3. 起點篩選：僅從與 word[0] 匹配的格子開始 DFS

運行示意圖