LeetCode-079-单词搜索

单词搜索

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

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

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/word-search/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：回溯算法

首先，直接判断2种特殊场景：

如果要匹配的字符串为空，直接返回true；

如果board数组为空，直接返回false。

否则，先声明一个和board同样大小的boolean类型的数组，记录当前单元格是否已经走过，然后遍历board的每一个字符，对每一个字符和word第一个字符相等的时候，调用回溯方法进行判断以当前字符为起点是否能够匹配word字符串，如果能返回true，否则继续遍历下一个字符。最后，如果没有匹配成功，返回false。

public class LeetCode_079 {

    public static boolean exist(char[][] board, String word) {

        /**

         * 如果要匹配的字符串为空，直接返回true

         */

        if (word == null || word.length() == 0) {

            return true;

        }

        /**

         * 如果board数组为空，直接返回false

         */

        if (board == null || board.length == 0 || board[0].length == 0) {

            return false;

        }

        /**

         * 声明一个和board同样大小的boolean类型的数组，记录当前单元格是否已经走过

         */

        boolean[][] visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {

            for (int j = 0; j < board[0].length; j++) {

                /**

                 * 对每一个字符和word第一个字符相等的时候，调用方法进行判断

                 */

                if (board[i][j] == word.charAt(0) && exist(board, visited, word, i, j, 0)) {

                    return true;

                }

            }

        }

        return false;

    }

    /**

     * 回溯算法

     *

     * @param board   原字符网格

     * @param visited 和board大小相同的boolean类型的网格，标识当前字符是否走过

     * @param word    要匹配的单词

     * @param startX  当前单元格的x坐标

     * @param startY  当前单元格的y坐标

     * @param pos     当前已经匹配了几个字符

     * @return

     */

    private static boolean exist(char[][] board, boolean[][] visited, String word, int startX, int startY, int pos) {

        if (board[startX][startY] != word.charAt(pos)) {

            // 如果当前单元格和要匹配的字符不同，直接返回false

            return false;

        } else if (pos == word.length() - 1) {

            // 如果已经匹配的字符数和word的长度相等，则说明已经匹配成功，返回true

            return true;

        }

        visited[startX][startY] = true;

        // 当前单元格可以往四个方向移动

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        boolean result = false;

        for (int[] dir : directions) {

            int nextStartX = startX + dir[0], nextStartY = startY + dir[1];

            if (nextStartX >= 0 && nextStartX < board.length && nextStartY >= 0 && nextStartY < board[0].length) {

                if (!visited[nextStartX][nextStartY]) {

                    boolean flag = exist(board, visited, word, nextStartX, nextStartY, pos + 1);

                    if (flag) {

                        result = true;

                        break;

                    }

                }

            }

        }

        visited[startX][startY] = false;

        return result;

    }

    public static void main(String[] args) {

        char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};

        // 测试用例，期望返回： true

        System.out.println(exist(board, "ABCCED"));

    }

}

【每日寄语】 逆境、是非来临，心中要持一“宽”字。

巴特西

LeetCode-079-单词搜索

单词搜索

解法一：回溯算法

最新文章

热门文章