LeetCode百题【单词搜索】

题目描述

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

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

示例 1：

1 2	`输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true`

示例 2：

1 2	`输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true`

示例 3：

1 2	`输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false`

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶： 你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解法

回溯法

class Solution {
    public boolean exist(char[][] board, String word) {
        int row = board.length;//行
        int col = board[0].length;//列
        boolean[][] visited = new boolean[row][col];//标识单次路径搜索是否访问过当前元素
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //遍历单词在字母板的起始地址
                boolean flag = check(board, word, visited, i, j, 0);
                if (flag == true) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * dfs
     *
     * @param board   字母板
     * @param word    匹配单词
     * @param visited 单次路径搜索是否经过
     * @param i       位置x
     * @param j       位置y
     * @param k       第几个字符
     * @return
     */
    public boolean check(char[][] board, String word, boolean[][] visited, int i, int j, int k) {
        //1.定义递归出口
        if (board[i][j] != word.charAt(k)) {
            //先判断是否相等
            return false;
        } else if (k == word.length() - 1) {
            //假如是最后一个，直接返回
            return true;
        }

        boolean result = false;
        visited[i][j] = true;//标识当前已经访问过
        int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};//移动方向  上下左右

        for (int[] dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            //x,y在可行范围内[0,len-1]
            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
                //同一起点下之前是否访问过当前位置
                if (!visited[x][y]) {
                    boolean flag = check(board, word, visited, x, y, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }

}