LeetCode79. 单词搜索

题目

描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

题解

深搜出路径做些小剪枝就好了
找到第一个点然后向四周搜索看有没有第二个点，如果没有返回继续寻找第一个点，如果找到再向四周找有没有第三个点如果有后面依次搜索没有返回上一级
第一次用注释部分代码用for 来循环四周的点 17ms，然后各种尝试之后想到可能是for里判断过多后面分开来写只有10ms

代码

    int[][] vis;
    String sWord;
    char[][] map;
    int num;

    public boolean exist(char[][] board, String word) {
        num = word.length();
        if (board.length == 0)
            return false;
        if (num == 0)
            return true;
        if (board.length * board[0].length < num)
            return false;
        sWord = word;
        map = board;
        vis = new int[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (word.charAt(0) == board[i][j]) {
                    vis[i][j] = 1;
                    if (dfs(i, j, 1))
                        return true;
                    vis[i][j] = 0;
                }
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int index) {

//        int[][] dict = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
//        for (int k = 0; k < 4; k++) {
//            int c = x + dict[k][0];
//            int l = y + dict[k][1];
//            if (c >= 0 && c < vis.length && l >= 0 && l < vis[0].length && vis[c][l] == 0 && map[c][l] == sWord.charAt(index)) {
//                if (index == num - 1)
//                    return true;
//                vis[c][l] = 1;
//                if (dfs(c, l, index + 1))
//                    return true;
//                vis[c][l] = 0;
//            }
//        }

        if (num == index)
            return true;
        if (x - 1 >= 0 && vis[x - 1][y] == 0 && map[x - 1][y] == sWord.charAt(index)) {
            if (index == num - 1)
                return true;
            vis[x - 1][y] = 1;
            if (dfs(x - 1, y, index + 1))
                return true;
            vis[x - 1][y] = 0;
        }
        if (x + 1 < map.length && vis[x + 1][y] == 0 && map[x + 1][y] == sWord.charAt(index)) {
            if (index == num - 1)
                return true;
            vis[x + 1][y] = 1;
            if (dfs(x + 1, y, index + 1))
                return true;
            vis[x + 1][y] = 0;
        }
        if (y + 1 < map[0].length && vis[x][y + 1] == 0 && map[x][y + 1] == sWord.charAt(index)) {
            if (index == num - 1)
                return true;
            vis[x][y + 1] = 1;
            if (dfs(x, y + 1, index + 1))
                return true;
            vis[x][y + 1] = 0;
        }
        if (y - 1 >= 0 && vis[x][y - 1] == 0 && map[x][y - 1] == sWord.charAt(index)) {
            if (index == num - 1)
                return true;
            vis[x][y - 1] = 1;
            if (dfs(x, y - 1, index + 1))
                return true;
            vis[x][y - 1] = 0;
        }

        return false;
    }

结果

image.png

最后编辑于：2019.08.09 17:54:53