JAVA DFS getting stack overflow error on a very large test case. Could you please help?


  • 0
    3

    My idea is simple. Using DFS to first flip the edge O's and the adjacent O's to #, then flip the remaining O's to X and flip back # to O. But I got the java.lang.stackoverflow error in a very large test case. I could not figure out why. Thanks in advance for your help!

    public void solve(char[][] board) {
        if(board.length == 0) return;
        int m = board.length, n = board[0].length;
        //flip all O on the edges and the adjacent O to #
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || i == m-1 || j == 0 || j == n-1) {
                    if(board[i][j] == 'O') dfs(board, i, j, '#');
                }
            }
        }
        //flip back # to O
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
    
    public void dfs(char[][] board, int i, int j, char replace) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
    
        if(board[i][j] == 'O') {
            board[i][j] = replace;
            dfs(board, i-1, j, replace);
            dfs(board, i+1, j, replace);
            dfs(board, i, j-1, replace);
            dfs(board, i, j+1, replace);
        }
    }

  • 0
    C

    Hi, did you figure out why?Because I seem to get the same problem here.


  • 0
    D

Log in to reply
 

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