题目描述      

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

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

示例

题解

       做过很多回溯的题目了，但这道题搞了好久，大概是以下几个原因：

1. 在回溯与动态规划之间犹豫。
2. 没get到需要先寻找回溯入口。
3. 忘了return，我也不知道当时咋想的。

代码

class Solution {public boolean exist(char[][] board, String word) {// 一个与board等大的数组，用于记录每个点是否已被归入结果集int[][] visited = new int[board.length][board[0].length];// 首先遍历寻找回溯入口for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == word.charAt(0)) {visited[i][j] = 1;if (deep(board, visited, word, 1, i, j)) {return true;}visited[i][j] = 0;}}}return false;}public boolean deep(char[][] board, int[][] visited, String word, int loop, int i, int j) {// 使用数组设置偏移量int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};if (loop == word.length()) {return true;}for (int k = 0; k < 4; k++) {int x = i + directions[k][0];int y = j + directions[k][1];if (inArea(x, y, board) && board[x][y] == word.charAt(loop) && visited[x][y] != 1) {visited[x][y] = 1;//注意返回！！！一直不对，查了很久，发现没写这句returnif (deep(board, visited, word, loop + 1, x, y)) {return true;}// 回溯标准的回置操作visited[x][y] = 0;}}return false;}/*** 判断坐标是否合法*/public boolean inArea(int x, int y, char[][] board) {return (x >= 0) && (x < board.length) && (y >= 0) && (y < board[0].length);}
}

性能

注意点

        遇到每个点不可重复使用的情况，谨记构造相同的数据结构来记录是否已访问。

        使用数组设置偏移量，简洁又方便。

        // 使用数组设置偏移量int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};