LeetCode Word Search：矩陣 DFS 回溯查找單詞

題目

給定 m×n 字符矩陣 board 和字符串 word，判斷能否在矩陣中按上下左右相鄰順序找到 word。同一格子不可重複使用。

DFS + 回溯

• 從每個格子 (i,j) 作為起點嘗試匹配 word[0]。
• 遞歸函數 dfs(i, j, k)：當前位置 (i,j) 匹配 word[k]。
  • 越界/已訪問/字符不匹配 → false。
  • k == len-1 → 全匹配成功 → true。
  • 標記 vis[i][j]=true，向四方向遞歸 k+1，任一方向成功即返回 true。
  • 回溯：vis[i][j]=false，返回結果。

Java 完整代碼

public class WordSearch {
    private char[] word;
    private int L, M, N;
    private char[][] board;
    private boolean[][] vis;

    public boolean exist(char[][] board, String word) {
        if (word == null || word.isEmpty() || board == null || board.length == 0) return false;
        this.word = word.toCharArray();
        this.L = word.length();
        this.board = board;
        this.M = board.length;
        this.N = board[0].length;
        this.vis = new boolean[M][N];

        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j)
                if (dfs(i, j, 0)) return true;
        return false;
    }

    private boolean dfs(int i, int j, int k) {
        if (i < 0 || i >= M || j < 0 || j >= N || vis[i][j]) return false;
        if (board[i][j] != word[k]) return false;
        if (k == L - 1) return true;

        vis[i][j] = true;
        boolean ok = dfs(i-1, j, k+1) || dfs(i+1, j, k+1)
                  || dfs(i, j-1, k+1) || dfs(i, j+1, k+1);
        vis[i][j] = false;
        return ok;
    }
}

優化技巧

1. 字符頻率剪枝：統計 board 中各字符數，若 word 需求超過供給 → 直接 false。
2. 反向搜索：若 word 末尾字符在板上出現頻率較低，可反轉 word 從稀有字符開始搜，減少遞歸分支。
3. 原地修改代替 vis 數組：將 board[i][j] = '#' 標記，回溯時恢復，節省 O(mn) 空間。

複雜度

• 時間：最壞 O(mn × 3^L)（每步最多 3 向延伸），實際受字符匹配強剪枝。
• 空間：O(mn) 訪問標記 + O(L) 遞歸棧。

總結

矩陣搜索詞彙是 DFS 回溯經典模板。關鍵點：訪問標記 + 回溯恢復、邊界檢查、提前剪枝。面試中先寫基本版，再補充優化討論，展示工程思維。