LeetCode/79. 单词搜索

79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

• board 和 word 中只包含大写和小写英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题思想其实很简单，就是在board限制的范围内，你去上下左右进行搜索，匹配word字符串，每一行每一行的匹配，本质上还是回溯的思想。

具体代码如下：

class Solution {
    public boolean exist(char[][] board, String word) {
      	//类似于二维数组的深度优先所有遍历
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean backtrack(char[][] board, String word, int x, int y, int start) {
        //判断是否越界，如果越界直接返回false
      	//同时判断当前字母是不是word中符合条件的字母，如果不是直接返回false
        if (x >= board.length || x < 0 || y >= board[0].length || y < 0 || board[x][y] != word.charAt(start)) {
            return false;
        }
      
        //如果start == word.length - 1证明查找结束
      	//这里由于上边已经判断了board[x][y] 是否等于 word.charAt(start)
      	//所以到这一步说明字母是满足条件的
        if (start == word.length() - 1) {
            return true;
        }

        //保存当前值用于结束递归的时候复原
        char temp = board[x][y];
        //这里使用这样的方法就可以不用创建二维的标记数组
      	//这是为了防止向右搜索后又向左搜索出现死循环的情况
        board[x][y] = '#';
        boolean result = backtrack(board, word, x + 1, y, start + 1) || backtrack(board, word, x - 1, y, start + 1)
                || backtrack(board, word, x, y + 1, start + 1) || backtrack(board, word, x, y - 1, start + 1);
        board[x][y] = temp;
        return result;
    }
}