題目鏈接

79.單詞搜索

class Solution {int m, n;public boolean exist(char[][] board, String word) {m = board.length;n = board[0].length;boolean[][] visited = new boolean[m][n];// 遍歷網格中的每個單元格作為搜索起點for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 從當前單元格開始深度優先搜索if (backtracking(board, word, visited, i, j, 0))return true;}}return false;}public boolean backtracking(char[][] board, String word, boolean[][] visited, int i, int j, int index) {if (index == word.length()) {return true;}// 剪枝條件：坐標越界/已訪問/當前字符不匹配if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index)) {return false;}visited[i][j] = true;// 向四個方向遞歸搜索if (backtracking(board, word, visited, i + 1, j, index + 1) ||backtracking(board, word, visited, i - 1, j, index + 1) ||backtracking(board, word, visited, i, j + 1, index + 1) ||backtracking(board, word, visited, i, j - 1, index + 1))return true;visited[i][j] = false;return false;}
}

小結：由于不能重復，先定義一個標記數組，以每個單元格作為搜索起點開始深度優先搜索，并在回溯中向上下左右四個方向遞歸搜索。