題目
#

題目簡述
#

給一個 m×n 的字元二維陣列 board 和一個字串 word，判斷 word 是否存在於 board 中。
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中「相鄰」單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

範例
#

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

概念圖示
#

Example 1: 搜尋 “ABCCED”
#

原始矩陣：
┌───┬───┬───┬───┐
│ A │ B │ C │ E │
├───┼───┼───┼───┤
│ S │ F │ C │ S │
├───┼───┼───┼───┤
│ A │ D │ E │ E │
└───┴───┴───┴───┘

搜尋路徑：
┌───┬───┬───┬───┐
│ A₁│ B₂│ C │ E │  ← 步驟 1-2: A→B
├───┼───┼───┼───┤
│ S │ F │ C₄│ S │  ← 步驟 3: C
├───┼───┼───┼───┤
│ A │ D₆│ E₅│ E │  ← 步驟 4-5: E→D
└───┴───┴───┴───┘

結果：找到 "ABCCED" ✓

Example 2: 搜尋 “SEE”
#

原始矩陣：
┌───┬───┬───┬───┐
│ A │ B │ C │ E │
├───┼───┼───┼───┤
│ S │ F │ C │ S │
├───┼───┼───┼───┤
│ A │ D │ E │ E │
└───┴───┴───┴───┘

搜尋路徑：
┌───┬───┬───┬───┐
│ A │ B │ C │ E │
├───┼───┼───┼───┤
│ S₁│ F │ C │ S₃│  ← 步驟 1,3: S→S
├───┼───┼───┼───┤
│ A │ D │ E₂│ E │  ← 步驟 2: E
└───┴───┴───┴───┘

結果：找到 "SEE" ✓

Example 3: 搜尋 “ABCB” (失敗案例)
#

原始矩陣：
┌───┬───┬───┬───┐
│ A │ B │ C │ E │
├───┼───┼───┼───┤
│ S │ F │ C │ S │
├───┼───┼───┼───┤
│ A │ D │ E │ E │
└───┴───┴───┴───┘

嘗試路徑：
┌───┬───┬───┬───┐
│ A₁│ B₂│ C₃│ E │  ← 步驟 1-3: A→B→C
├───┼───┼───┼───┤
│ S │ F │ C │ S │  ← 無法找到第二個 B
├───┼───┼───┼───┤
│ A │ D │ E │ E │
└───┴───┴───┴───┘

結果：無法找到 "ABCB" ✗

DFS 搜尋說明：

數字標示：表示字母在單詞中的順序
箭頭方向：表示 DFS 的搜尋方向（上下左右）
相鄰規則：只能從當前位置向四個方向移動
回溯機制：當路徑不通時，會回到上一步嘗試其他方向

解題思路
#

這題要求我們在二維字元陣列中搜尋指定的單詞。我們可以使用深度優先搜尋（DFS）來解決這個問題，通過遍歷每個可能的起始位置，然後使用 DFS 來搜尋單詞的其餘部分。

解法
#

DFS

定義四個方向：上、下、左、右
遍歷矩陣中的每個位置，如果該位置的字母等於單詞的第一個字母，則開始 DFS 搜尋
在 DFS 中，檢查邊界條件、訪問狀態和字母匹配
如果找到完整的單詞，返回 true；否則回溯並繼續搜尋

步驟
#

初始化方向陣列：
- 定義四個方向：{{1,0}, {-1,0}, {0,1}, {0,-1}}
遍歷起始位置：
- 遍歷矩陣中的每個位置 (i,j)
- 如果 board[i][j] == word.charAt(0)，開始 DFS 搜尋
DFS 搜尋：
- 檢查邊界條件和訪問狀態
- 如果字母匹配，標記為已訪問
- 遞迴搜尋四個方向
- 回溯時取消標記

例子說明
#

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

步驟	操作	當前位置	已匹配字母	說明
初始化	-	-	""	開始搜尋
找到起始位置	發現 `board[0][0] = 'A'`	(0,0)	“A”	開始 DFS 搜尋
DFS 步驟 1	向右搜尋	(0,1)	“AB”	找到 ‘B’
DFS 步驟 2	向下搜尋	(1,1)	“ABC”	找到 ‘C’
DFS 步驟 3	向右搜尋	(1,2)	“ABCC”	找到 ‘C’
DFS 步驟 4	向下搜尋	(2,2)	“ABCCE”	找到 ‘E’
DFS 步驟 5	向左搜尋	(2,1)	“ABCCED”	找到 ‘D’

最終結果： true，找到完整單詞 “ABCCED”

搜尋路徑： (0,0) → (0,1) → (1,1) → (1,2) → (2,2) → (2,1)

完整程式碼
#

java

class Solution {
    // 定義四個方向：下、上、右、左
    int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        // 創建訪問標記陣列
        boolean[][] visited = new boolean[m][n];

        // 遍歷每個可能的起始位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果找到單詞的第一個字母，開始 DFS 搜尋
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, word, i, j, 0, visited)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        // 如果已經匹配完所有字母，返回 true
        if (index == word.length()) {
            return true;
        }

        int m = board.length;
        int n = board[0].length;

        // 檢查邊界條件、訪問狀態和字母匹配
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 標記當前位置為已訪問
        visited[i][j] = true;

        // 搜尋四個方向
        boolean found = false;
        for (int[] dir : dirs) {
            if (dfs(board, word, i + dir[0], j + dir[1], index + 1, visited)) {
                found = true;
                break;
            }
        }

        // 回溯時取消標記
        visited[i][j] = false;
        return found;
    }
}