Problem: 79. 單詞搜索
給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在于網格中，返回 true ；否則，返回 false 。
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

整體思路

這段代碼旨在解決一個經典的二維網格搜索問題：單詞搜索 (Word Search)。其核心功能是判斷一個給定的單詞 word 是否存在于一個字符網格 board 中。構成單詞的路徑規則是：字母必須在網格中水平或垂直相鄰，并且同一個單元格的字母在路徑中不允許被重復使用。

該算法采用了 深度優先搜索（DFS） 結合 回溯（Backtracking） 的策略。其整體思路可以分解為以下幾個步驟：

1. 主驅動邏輯（遍歷所有起點）：

   • exist 方法是算法的入口。它通過兩層嵌套的 for 循環遍歷網格 board 中的每一個單元格 (i, j)。
   • 這個遍歷的目的是將每一個單元格都視作單詞 word 的一個潛在 起始點。
   • 對于每一個起點，它都會調用核心的 dfs 輔助函數來嘗試進行深度搜索。如果任何一次 dfs 調用返回 true，意味著找到了完整的單詞路徑，程序立即返回 true。
   • 如果遍歷完所有可能的起點后，dfs 均未成功，則說明單詞不存在于網格中，程序最后返回 false。

2. 核心搜索邏輯（DFS 與回溯）：

   • dfs(i, j, k, ...) 是一個遞歸函數，負責從單元格 (i, j) 開始，嘗試匹配 word 中從第 k 個字符開始的剩余部分。
   • 剪枝與基準情況：
     • 失敗剪枝：如果當前單元格 (i, j) 超出邊界（在遞歸調用前檢查），或者其字符 board[i][j] 與目標字符 word[k] 不匹配，則此路不通，直接返回 false。
     • 成功基準：如果當前字符匹配，并且這已經是單詞的最后一個字符（k == word.length - 1），則說明整個單詞已經成功匹配，返回 true。
   • 遞歸與回溯：
     • 標記（Marking）：為了防止在同一路徑中重復使用單元格，在深入探索之前，代碼會將當前單元格 board[i][j] 的值臨時修改為一個特殊標記（如此代碼中的 0）。這相當于一個“正在訪問”的標記。
     • 探索（Exploration）：接著，代碼會向當前單元格的四個相鄰方向（上、下、左、右）進行遞歸調用 dfs(x, y, k + 1, ...)，嘗試匹配單詞的下一個字符。
     • 回溯（Backtracking）：在四個方向的遞歸探索完成之后（無論成功還是失敗），必須將當前單元格 board[i][j] 的值恢復為其原始字符 word[k]。這是回溯算法的精髓，它確保了在探索其他起始點的路徑時，該單元格是可用的。
     • 如果四個方向的探索都沒有找到完整的路徑，則從當前點出發的搜索失敗，返回 false。

完整代碼

class Solution {// 定義一個常量數組，用于表示四個方向的坐標偏移量：右、左、下、上private static final int[][] DIRECTION = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};/*** 在二維字符網格中查找是否存在一個給定的單詞。* @param board 二維字符網格* @param word  要查找的單詞* @return 如果單詞存在，返回 true；否則，返回 false。*/public boolean exist(char[][] board, String word) {// 將目標單詞轉換為字符數組，以提高后續字符訪問的效率char[] w = word.toCharArray();// 遍歷網格中的每一個單元格，將其作為單詞搜索的潛在起點for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {// 從 (i, j) 開始進行深度優先搜索，嘗試匹配單詞的第一個字符 (k=0)if (dfs(i, j, 0, board, w)) {// 如果找到了一個完整的路徑，立即返回 truereturn true;}}}// 如果遍歷完所有可能的起點都未能找到單詞，則返回 falsereturn false;}/*** 深度優先搜索輔助函數。* @param i      當前搜索的行索引* @param j      當前搜索的列索引* @param k      當前要匹配的目標單詞中的字符索引* @param board  字符網格* @param word   目標單詞的字符數組* @return 如果從 (i, j) 出發能找到 word[k...] 的路徑，返回 true*/private boolean dfs(int i, int j, int k, char[][] board, char[] word) {// 剪枝：如果當前單元格的字符與目標字符不匹配，此路不通if (board[i][j] != word[k]) {return false;}// 成功基準：如果當前字符匹配，并且已是單詞的最后一個字符，則搜索成功if (k == word.length - 1) {return true;}// 關鍵【標記】步驟：將當前單元格標記為已訪問，防止在同一路徑中重復使用。// 這里用一個非字符值（如0）來標記，也可以用一個不會在 board 和 word 中出現的特殊字符。board[i][j] = 0; // 探索四個相鄰的方向for (int[] dir : DIRECTION) {int x = dir[0] + i;int y = dir[1] + j;// 檢查新坐標 (x, y) 是否在網格邊界內if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {// 對有效的相鄰單元格進行遞歸調用，嘗試匹配單詞的下一個字符 (k+1)if (dfs(x, y, k + 1, board, word)) {// 如果任意方向的遞歸探索成功，立即返回 truereturn true;}}}// 關鍵【回溯】步驟：恢復當前單元格的原始值。// 這樣，在回溯到上一個狀態后，其他分支的搜索路徑仍然可以使用此單元格。board[i][j] = word[k];// 如果所有方向都探索完畢，仍未找到匹配路徑，則返回 falsereturn false;}
}

時空復雜度

時間復雜度：O(M * N * 3^L)

1. 外層循環：exist 方法中的兩層 for 循環遍歷了整個網格，這部分是 M * N 次操作，其中 M 是行數，N 是列數。
2. DFS 復雜度：對于每個起點，都會調用 dfs 函數。在 dfs 函數中，每次遞歸都會向最多 3 個新的方向探索（因為不能走回頭路，而修改 board 值的操作天然地防止了這一點）。
3. 遞歸深度：遞歸的最大深度由單詞的長度 L 決定。
4. 綜合分析：
   • 在最壞的情況下，對于網格中的每個單元格 (M * N)，我們都可能啟動一次深度優先搜索。
   • 每次搜索的計算量大致可以估算為 3^L，因為每一步都有最多3個選擇，持續 L 步。
   • 因此，總的時間復雜度是一個粗略的上限：O(M * N * 3^L)，其中 L 是單詞 word 的長度。

空間復雜度：O(L)

1. 主要存儲開銷：算法的額外空間開銷主要來自于遞歸調用棧。
2. 遞歸深度：dfs 函數的遞歸深度取決于正在匹配的單詞的長度。在最壞的情況下，當成功匹配到單詞的最后一個字母時，遞歸棧的深度會達到 L。
3. 其他變量：
   • w = word.toCharArray(): 占用了 O(L) 的空間。
   • DIRECTION 數組：占用 O(1) 的常數空間。
   • 遞歸函數中的局部變量：占用 O(1) 空間。

綜合分析：
遞歸棧的深度是空間復雜度的主要部分。因此，算法的空間復雜度為 O(L)，其中 L 是單詞 word 的長度。

參考靈神