题目

image.png

思路

  • 回溯

    代码

    1. public boolean exist(char[][] board, String word) {
    2.       boolean res = false;
    3.       for (int i = 0; i < board.length; i++) {
    4.           for (int j = 0; j < board[0].length; j++) {
    5.               if (board[i][j] == word.charAt(0)) {
    6.                   if (dfs(board, i, j, word, 0))
    7.                       return true;
    8.               }
    9.           }
    10.       }
    11.       return false;
    12.   }
    14.   public boolean dfs(char[][] board, int i ,int j, String word, int index) {
    15.       if (index >= word.length()) return true;
    16.       if (i < 0 || j < 0 || i >= board.length || j >= board[0].length
    17.           || board[i][j] != word.charAt(index)) return false;
    18.       board[i][j] += 256;
    19.       index = index + 1;
    20.       boolean res = dfs(board, i - 1, j, word, index) || dfs(board, i, j - 1, word, index)
    21.                       || dfs(board, i + 1, j, word, index) || dfs(board, i, j + 1, word, index);
    22.       board[i][j] -= 256;
    23.       return res;
    24.   }

    单词搜索