leetcode链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

题目

image.png

解法

使用 dfs（深度遍历搜索）

  1. class Solution {
  2.     public boolean exist(char[][] board, String word) {
  3.         // 行数
  4.         int row = board.length;
  5.         // 列数
  6.         int col = board[0].length;
  8.         char[] chars = word.toCharArray();
  9.         for (int i = 0; i < row; i++) {
  10.             for (int j = 0; j < col; j++) {
  11.                 if (dfs(board, chars, i, j, 0)) {
  12.                     return true;
  13.                 }
  14.             }
  15.         }
  16.         return false;
  17.     }
  19.     boolean dfs(char[][] board, char[] word, int i, int j, int index) {
  20.         // 参数说明，index指查到字符串的第几个字符
  21.         // 边界判断
  22.         // 1.如果越界直接返回false
  23.         // 2.如果当前字符不等于board[i][j]，说明此路不通，返回false
  24.         if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[index]) {
  25.             return false;
  26.         }
  28.         // 如果index=word.length，说明匹配成功，返回true
  29.         if (index == word.length-1 ) {
  30.             return true;
  31.         }
  33.         // 保存中间值，方便复原
  34.         char tmp = board[i][j];
  35.         // 将当前位置标记为已访问
  36.         board[i][j] = '.';
  37.         boolean res = dfs(board, word, i - 1, j, index + 1) ||
  38.                 dfs(board, word, i + 1, j, index + 1) ||
  39.                 dfs(board, word, i, j - 1, index + 1) ||
  40.                 dfs(board, word, i, j + 1, index + 1);
  41.         // 复原环境
  42.         board[i][j] = tmp;
  43.         return res;
  44.     }
  45. }