題目：給定一個(gè) m x n 二維字符網(wǎng)格board 和一個(gè)字符串單詞 word 蛇捌。如果 word 存在于網(wǎng)格中百姓，返回 true 笛洛；否則，返回 false 咐蚯。
單詞必須按照字母順序童漩，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格春锋。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用矫膨。
示例 1：
image.png
輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true
示例 2：
image.png
輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
輸出：true
示例 3：
image.png
輸入：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 僅由大小寫(xiě)英文字母組成
進(jìn)階：你可以使用搜索剪枝的技術(shù)來(lái)優(yōu)化解決方案，使其在 board 更大的情況下可以更快解決問(wèn)題期奔？
相關(guān)標(biāo)簽：數(shù)組侧馅、回溯、矩陣
解析：這題大體思路就是先找到單詞的起點(diǎn)位置呐萌，然后根據(jù)上下左右四個(gè)方向找符合條件的字符馁痴，同時(shí)考慮到不能重復(fù)使用同一個(gè)位置的字符這個(gè)條件，可以把訪問(wèn)過(guò)的路徑的字符置為*號(hào)肺孤，遍歷過(guò)后替換回來(lái)罗晕。具體代碼如下所示：
public boolean exist(char[][] board, String word) {
char[] arr = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if(dfs(board,arr,i,j,0)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board,char[] arr,int i,int j,int index){
//判斷邊界條件（中斷條件）
if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=arr[index]){
return false;
}
//如果遍歷完成(結(jié)束條件）
if(index == arr.length-1){
return true;
}
//保存當(dāng)前表格里的字符
char temp = board[i][j];
//將走過(guò)的路徑設(shè)置成*，防止重復(fù)
board[i][j] = '*';
//繼續(xù)判斷上下左右四個(gè)方向
boolean top = dfs(board,arr,i-1,j,index+1);
boolean bottom = dfs(board,arr,i+1,j,index+1);
boolean right = dfs(board,arr,i,j+1,index+1);
boolean left = dfs(board,arr,i,j-1,index+1);
//將之前替換的字符還原
board[i][j] = temp;
return top || bottom || right || left;
}
每天進(jìn)步一點(diǎn)點(diǎn)~
