题目

题解

代码

代码一:

public class code79 {

    public static boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        boolean visited[][] = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(i, j, 0, word, visited, board)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(int i, int j, int idx, String word, boolean visited[][], char board[][]) {
        if (idx == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)
                || visited[i][j]) {
            return false;
        }

        visited[i][j] = true;
        if (dfs(i + 1, j, idx + 1, word, visited, board) || dfs(i, j + 1, idx + 1, word, visited, board)
                || dfs(i - 1, j, idx + 1, word, visited, board) || dfs(i, j - 1, idx + 1, word, visited, board)) {
            return true;
        }
        visited[i][j] = false;

        return false;
    }

    public static void main(String[] args) {
        char board[][] = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } };

        String word_1 = "ABCCED";
        String word_2 = "SEE";
        String word_3 = "ABCB";
        String word_4 = "ABFDECCESE";

        boolean flag_1 = exist(board, word_1);
        boolean flag_2 = exist(board, word_2);
        boolean flag_3 = exist(board, word_3);
        boolean flag_4 = exist(board, word_4);

        System.out.println(flag_1);
        System.out.println(flag_2);
        System.out.println(flag_3);
        System.out.println(flag_4);
    }
}

代码二:

public class code79 {

    // x-1,y
    // x,y-1 x,y x,y+1
    // x+1,y
    public static int direction[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

    public static boolean exist(char[][] board, String word) {
        int m = board.length;
        if (m == 0) {
            return false;
        }
        int n = board[0].length;
        boolean visited[][] = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0, word, visited, board)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(int i, int j, int count, String word, boolean visited[][], char board[][]) {
        if (count == word.length() - 1) {
            return board[i][j] == word.charAt(count);
        }
        if (board[i][j] == word.charAt(count)) {
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int dx = i + direction[k][0];
                int dy = j + direction[k][1];
                if (inArea(dx, dy, board) && !visited[dx][dy]) {
                    if (dfs(dx, dy, count + 1, word, visited, board)) {
                        return true;
                    }
                }
            }
            visited[i][j] = false;
        }
        return false;
    }

    public static boolean inArea(int x, int y, char board[][]) {
        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        char board[][] = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } };

        String word_1 = "ABCCED";
        String word_2 = "SEE";
        String word_3 = "ABCB";
        String word_4 = "ABFDECCESE";

        boolean flag_1 = exist(board, word_1);
        boolean flag_2 = exist(board, word_2);
        boolean flag_3 = exist(board, word_3);
        boolean flag_4 = exist(board, word_4);

        System.out.println(flag_1);
        System.out.println(flag_2);
        System.out.println(flag_3);
        System.out.println(flag_4);
    }
}

79. 单词搜索

题目

题解

代码

代码一:

代码二:

参考