Share my Java standard DFS solution


  • 1
    M
    // Standard DFS solution
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) return false;
        if (board == null || board.length == 0 || board[0].length == 0) return false;
        char[] chars = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int row = 0 ; row < board.length ; row++) {
            for (int col = 0 ; col < board[row].length ; col++) {
                if (board[row][col] == chars[0]) {
                    boolean found = search(board, row, col, visited, chars, 0);
                    if (found) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    private boolean search(char[][] board, int row, int col, boolean[][] visited, char[] chars, int index) {
        if (index == chars.length) return true;
        if (row < 0 || row >= board.length) return false;
        if (col < 0 || col >= board[0].length) return false;
        if (visited[row][col]) return false;
        visited[row][col] = true;
        boolean found = false;
        if (board[row][col] == chars[index]) {
            found = search(board, row - 1, col, visited, chars, index + 1)
                 || search(board, row + 1, col, visited, chars, index + 1)
                 || search(board, row, col - 1, visited, chars, index + 1)
                 || search(board, row, col + 1, visited, chars, index + 1);
        }
        // Clean up the trace of searching for next explore of another path
        visited[row][col] = false;
        return found;
    }

  • 0
    M

    your code and mine are almost exactly the same...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.