79.单词搜索

给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution { public boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); for(int i = 0; i < board.length; i++) { // 遍历所有行 for(int j = 0; j < board[0].length; j++) { // 遍历所有列 if (dfs(board, words, i, j, 0)) return true; // 从(i,j)开始搜索 } } return false; // 所有起点都找不到 } public boolean dfs(char[][] board, char[] word, int i, int j, int k) { // 边界检查 + 字符匹配检查 if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false; // 成功匹配到最后一个字符 if (k == word.length - 1) return true; // 标记当前位置为已访问（用'\0'占位） board[i][j] = '\0'; // 向四个方向继续搜索 boolean res = dfs(board, word, i + 1, j, k + 1) // 向下 || dfs(board, word, i - 1, j, k + 1) // 向上 || dfs(board, word, i, j + 1, k + 1) // 向右 || dfs(board, word, i, j - 1, k + 1); // 向左 // 恢复原始字符（回溯的关键步骤） board[i][j] = word[k]; return res; } }