LeetCode Word Search：二維網格單詞搜索 DFS 回溯完整解析

問題描述

給定 m×n 字符網格 board 和字符串 word，判斷 word 是否能由**相鄰單元格**（上下左右）順序構成，每個單元格最多使用一次。

DFS 回溯核心邏輯

從每個格子作為起點嘗試匹配：

1. 邊界檢查：越界 → false
2. 狀態檢查：已訪問或字符不匹配 → false
3. 標記訪問：visited[i][j] = true
4. 終止條件：已匹配到 word 最後一字符 → true
5. 四方向遞歸：任一方向返回 true 即整體 true
6. 回溯：visited[i][j] = false，返回 false

關鍵判斷順序（避坑指南）

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        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 boolean dfs(char[][] board, boolean[][] visited,
                        String word, int idx, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        if (visited[i][j] || board[i][j] != word.charAt(idx)) return false;
        visited[i][j] = true;
        if (idx == word.length() - 1) return true;
        if (dfs(board, visited, word, idx+1, i, j+1) ||
            dfs(board, visited, word, idx+1, i+1, j) ||
            dfs(board, visited, word, idx+1, i-1, j) ||
            dfs(board, visited, word, idx+1, i, j-1))
            return true;
        visited[i][j] = false;
        return false;
    }
}

複雜度分析

• 時間：O(m × n × 4ᴸ) — L = word.length()，每個起點最多 4ᴸ 路徑（實際大幅剪枝）
• 空間：O(m × n) visited 陣列 + O(L) 遞歸棧

優化技巧

• **頻率剪枝**：先統計 board 中字符頻率，若 word 中某字符出現次數超過 board，直接 false
• **反向搜索**：若 word 尾字符在 board 中較稀有，從尾向頭搜索減少分支
• **就地修改 board**：用特殊字符（如 #）標記訪問，省去 visited 陣列（需確保 board 字符集不含該字符）