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