题目链接

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;}
}

小结：由于不能重复，先定义一个标记数组，以每个单元格作为搜索起点开始深度优先搜索，并在回溯中向上下左右四个方向递归搜索。