79.单词搜索

题目

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

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

 

示例:

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

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

方法（回溯算法）

回溯法需要重点考察三个内容：

• 路径：记录我们当前匹配到了word中的哪个字符。我们用index表示当前匹配到的word字符的索引。
• 结束条件：当匹配到了word中的最后一个字符并且匹配成功时，回溯结束，返回true
• 选择：由于同一个单元格中的字母不能被重复使用，因此我们用一个矩阵uesd记录位置[i,j]上的字符是否被使用过。如果board的当前位置[i,j]上的字符与word的index位置上的字符匹配，那么就做选择（使用[i,j]位置上的元素）。做完选择之后，我们递归匹配board中的下一个位置字符是否与word的index+1位置上的字符匹配（下一个位置有上下左右四种可能的情况，如果这个下一个位置已经使用过，那么剪枝即可），最后撤销选择。

具体见代码注释

代码

class Solution {
    private char[][] board;
    private boolean[][] used;
    private String word;
    private boolean res = false;
    //代表往上下左右四个方向走
    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        used = new boolean[board.length][board[0].length];
        //以board矩阵中的每一个位置为起点开始，尝试能否和word匹配
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(backtrack(i, j, 0))
                    return true;
            }
        }
        return false;
    }

    public boolean backtrack(int i, int j, int index){
        //终止条件
        if(board[i][j] != word.charAt(index))
            return false;
        else if(index == word.length() - 1){
            return true;
        }
        //如果该位置元素和word中index位置上的元素相等，那么做选择（使用这个位置的元素）
        used[i][j] = true;
        //递归匹配下一个位置：下一个位置有上下左右四种情况
        for(int[] dir : direction){
            //newi和newj为下一个位置的坐标
            int newi = i + dir[0];
            int newj = j + dir[1];
            //下一个位置的坐标不能越界
            if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length){
                //如果下一个位置已经使用过，就直接跳过
                if(used[newi][newj])
                    continue;
                if(backtrack(newi, newj, index + 1)){
                    return true;
                }
            }
            
        }
        //撤销选择
        used[i][j] = false;
        return false;
    }
}