原题
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
原题url：https://leetcode-cn.com/problems/word-search/
解题
回溯
拿到这题，我一开始想到的方法就是：
- 以每一格为起点，开始寻找，寻找的条件是要保证当前的字母和下一个和它连接的字母（上下左右）都符合条件，那么就继续查找。
- 只要当前不符合，立刻返回 false，快速失败。
- 利用一个二维 boolean 数组记录每一格的使用情况，记住，如果从当前格出发都不成功的话，则需要
回退。
接下来看看代码：
class Solution {
// 总行数
int row;
// 总列数
int col;
// 原数组
char[][] board;
// 需要寻找的字符数组
char[] wordArray;
public boolean exist(char[][] board, String word) {
this.board = board;
this.row = board.length;
this.col = board[0].length;
this.wordArray = word.toCharArray();
// 标记每一格是否用过的二维数组
boolean[][] used = new boolean[row][col];
// 以每一格为起点开始搜索
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (dfs(i, j, 0, used)) {
return true;
}
}
}
return false;
}
public boolean dfs(int x, int y, int index, boolean[][] used) {
// 当前位置是否符合条件
if (board[x][y] != wordArray[index]) {
return false;
}
// 全部找完了
if (index == wordArray.length - 1) {
return true;
}
// 设置当前格使用过了
used[x][y] = true;
// 寻找上下左右是否有符合下一个的情况
// 上一格是否存在并且没有被使用过
if (x > 0 && !used[x - 1][y]) {
if (dfs(x - 1, y, index + 1, used)) {
return true;
}
}
// 下一格是否存在并且没有被使用过
if (x < row - 1 && !used[x + 1][y]) {
if (dfs(x + 1, y, index + 1, used)) {
return true;
}
}
// 左一格是否存在并且没有被使用过
if (y > 0 && !used[x][y - 1]) {
if (dfs(x, y - 1, index + 1, used)) {
return true;
}
}
// 右一格是否存在并且没有被使用过
if (y < col - 1 && !used[x][y + 1]) {
if (dfs(x, y + 1, index + 1, used)) {
return true;
}
}
// 上下左右的情况都走完了，因此回退，设置当前格没有使用过
used[x][y] = false;
return false;
}
}
提交OK，执行用时：19 ms，内存消耗：38.3 MB。从时间上看起来还有不少优化的空间，那该怎么做呢？
似乎无用的优化
我看了别人更优的解法，发现思想都是一致的，只是在判断上可能会更加简洁一些，如果是判断快速失败的话，似乎没有什么本质上的区别。我将自己的写法稍微优化了一下：
class Solution {
// 总行数
int row;
// 总列数
int col;
// 原数组
char[][] board;
// 需要寻找的字符数组
char[] wordArray;
public boolean exist(char[][] board, String word) {
this.board = board;
this.row = board.length;
this.col = board[0].length;
this.wordArray = word.toCharArray();
// 标记每一格是否用过的二维数组
boolean[][] used = new boolean[row][col];
// 以每一格为起点开始搜索
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (dfs(i, j, 0, used)) {
return true;
}
}
}
return false;
}
public boolean dfs(int x, int y, int index, boolean[][] used) {
// 当前位置不存在或者使用过，则返回失败
if (x < 0 || x >= row || y < 0 || y >= col || used[x][y]) {
return false;
}
// 当前位置是否符合条件
if (board[x][y] != wordArray[index]) {
return false;
}
// 全部找完了
if (index == wordArray.length - 1) {
return true;
}
// 设置当前格使用过了
used[x][y] = true;
// 寻找上下左右是否有符合下一个的情况
boolean flag = dfs(x - 1, y, index + 1, used) || dfs(x + 1, y, index + 1, used) ||
dfs(x, y - 1, index + 1, used) || dfs(x, y + 1, index + 1, used);
// 上下左右的情况都走完了，因此回退，设置当前格没有使用过
used[x][y] = false;
return flag;
}
}
提交OK，执行用时：5 ms，内存消耗：38.4 MB。用时上少了很多，应该在于判断上：
- 针对位置是否存在的判断，之前的写法是判断下一个位置是否存在，分散在四个 if 判断中，现在是写在一个里面，用于判断当前位置。
- 寻找上下左右时，因为逻辑运算
||是支持短路的，所以和之前分在四个 if 中效果是差不多的，但看起来更加简洁。
好吧，其实我自己也没有看懂为什么这样写时间上会减少，大家如果知道的话，欢迎在下方留言。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要就是回溯，针对边界情况需要注意，应该就没有其他问题了。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
网友评论