原題鏈接：. - 力扣（LeetCode）

給定一個?m x n?二維字符網格?board?和一個字符串單詞?word?。如果?word?存在于網格中，返回?true?；否則，返回?false?。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

示例 1：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true

示例 2：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
輸出：true

示例 3：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
輸出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board?和?word?僅由大小寫英文字母組成

思路：

本題可采用回溯的方法解決。對于 word 字符串，每匹配到一個字符 word.charAt(p) 后（假設在 board[ i ][ j ] 處匹配到），就遞歸匹配下一個字符 word.charAt(p+1)（在 board[ i ][ j + 1]、board[ i ][ j - 1]、board[ i +1 ][ j ]、board[ i +1 ][ j ] 處去嘗試匹配），如此類推。同時注意到對已經匹配的字符需要加一個標識，避免其被再次匹配到（可以給已經匹配的字符加一個 - 號，讓其不能再和word 中的字符匹配到）。

終止條件：假如 p == word.length()，則說明匹配成功。將 found 設置為 true，返回。假如 found 為 true，則說明之前已經匹配成功，返回，退出遞歸。假如 傳入的 i,j 不在 board 范圍內，返回。假如?board[ i ][ j ] 和 word.charAt(p) 不匹配，那么也退出當前這層遞歸，返回。

若匹配成功，則需要給 board[ i ][ j ] 加上一個已匹配的標識，然后去 board[ i ][ j ] 的上下左右四個方位去繼續匹配下一個字符。最后還需要取消標識，進行回溯。

代碼：

class Solution {boolean found = false;public boolean exist(char[][] board, String word) {int n = board.length,m=board[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){dfs(board,i,j,word,0);if(found){return true;}}}return false;}public void dfs(char[][] board,int i,int j,String word,int p){//word已經被匹配完畢，匹配成功if(p==word.length()){found = true;return;}if(found){return;}int n = board.length, m = board[0].length;if(i<0||j<0||i>=n||j>=m){return;}//若(i,j)處的字符不匹配word[p]if(board[i][j]!=word.charAt(p)){return;}//board(i,j)處的字符匹配上了word[p]//做個標記，避免匹配上的字符再被匹配board[i][j]= (char)(-board[i][j]);dfs(board,i,j-1,word,p+1);dfs(board,i,j+1,word,p+1);dfs(board,i-1,j,word,p+1);dfs(board,i+1,j,word,p+1);board[i][j]= (char)(-board[i][j]);}
}