Why having stackoverflow error


  • 0
    I
    public class Solution {
    public void solve(char[][] board) {
        int row = board.length;
        if(row == 0)
            return;
        int col = board[0].length;
        // do DFS for those Os on boarder
        int i = 0; // first row
        for(int j = 0; j < col; j++){
            if(board[i][j] == 'O'){
                doDFS(board, i, j);
            }
        }
        i = row - 1; // last row
        for(int j = 0; j < col; j++){
            if(board[i][j] == 'O'){
                doDFS(board, i, j);
            }
        }
        int j = 0; // first column
        for(i = 0; i < row; i++){
            if(board[i][j] == 'O'){
                doDFS(board, i, j);
            }
        }
        j = col - 1; // last column
        for(i = 0; i < row; i++){
            if(board[i][j] == 'O'){
                doDFS(board, i, j);
            }
        }
        // do one time scan to finalize 
        for(i = 0; i < row; i++){
            for(j = 0; j < col; j++){
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                if(board[i][j] == 'R')
                    board[i][j] = 'O';
            }
        }
    }
    
    public void doDFS(char[][] board, int i, int j){
        int row = board.length;
        int col = board[0].length;
        if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O')
            return;
        board[i][j] = 'R'; // reachable
        doDFS(board, i, j+1);
        doDFS(board, i+1, j);
        doDFS(board, i-1, j);
        doDFS(board, i, j-1);
    }
    

    I got stackoverflow exception when submitting above code, the error was thrown when recursively invoking doDFS() method. I'm windering how would this happen? I googled online and found using BFS could get rid of this error, but I don't really see any huge difference between DFS and BFS in this problem since they both basically cover all the entries in the board. Can anyone help explain? Thanks


  • 7
    J

    Cuz those people sucks dick.

    I GOT THAT FUCKNG PROBLEM 2.

    System.fuck();

  • 0
    Z

    Maybe this is what you want.

    https://oj.leetcode.com/discuss/1723/my-code-can-not-pass-this-longest-case

    I have got this too. Your recursion have exhausted the stack. If you DO want to pass the longest case, try to use iteration instead of recursion.


  • 0
    S

    'cause recursion has caused stackOverflow lol ~ stack may help.


Log in to reply
 

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