DFS-based solution in Java


  • 0
    M
    public class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0) return;
            int height = board.length, width = board[0].length;
            for (int i = 0; i < width; ++i) {
                if (board[0][i] == 'O') dfs(board, 0, i);
                if (board[height - 1][i] == 'O') dfs(board, height - 1, i);
            }
            for (int i = 1; i < height - 1; ++i) {
                if (board[i][0] == 'O') dfs(board, i, 0);
                if (board[i][width - 1] == 'O') dfs(board, i, width - 1);  
            }
            for (int i = 0; i < height; ++i) {
                for (int j = 0; j < width; ++j) {
                    if (board[i][j] == 'O') board[i][j] = 'X';
                    else if (board[i][j] == 'V') board[i][j] = 'O';
                }
            }
        }
        
        private void dfs(char[][] board, int row, int col) {
            int height = board.length, width = board[0].length;
            board[row][col] = 'V';  // mark as visited
            if (row > 1 && board[row - 1][col] == 'O') dfs(board, row - 1, col);  // prevent stack overflow error
            if (row < height - 2 && board[row + 1][col] == 'O')dfs(board, row + 1, col);
            if (col > 1 && board[row][col - 1] == 'O') dfs(board, row, col - 1);
            if (col < width - 2 && board[row][col + 1] == 'O') dfs(board, row, col + 1);
        }
    }

  • 0
    Y

    Hello, Why make "row > 1" can prevent stack over flow?


  • 0
    M

    the first time i wrote this code, i got stack overflow error. because the base case i used was if (row < 0 || row >= board.length || ...) return, now row > 1, the recursion stops when row == 1, not row < 0 anymore, thus we can save 2 levels of recursive calls, that is when row == 0 and row == 1, we can prevent the stack frame of jvm from going deeper for 2 more levels, so the stack overflow error can be prevented. (this is actually a corner case -- you can also prevent the stack overflow error by adjusting the "max-recursion-levels-allowed" parameter of the jvm.)


Log in to reply
 

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