Use stack to get rid of StackOverFlow in DFS


  • 4
    D

    Most people first use a recursion to traverse in board, but this will cause StackOverFlow in large size input. Use a stack to simulate the recursion will solve your problem.

    class Pair {
        int x;
        int y;
        Pair (int a, int b) { x = a; y = b; }
    }
    
    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        int n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || j == 0 || i == m-1 || j == n-1)
                    && board[i][j] == 'O') {
                    // for positions in border which are 'O', exhaust all NON surrounded regions and mark them as 'N'
                    Stack<Pair> stk = new Stack<Pair>();
                    stk.push(new Pair(i, j));
                    while (!stk.isEmpty()) {
                        Pair curr = stk.pop();
                        int x = curr.x;
                        int y = curr.y;
                        if (x < 0 || x >= m || y < 0 || y >= n || !(board[x][y] == 'O'))
                            continue;
                        board[x][y] = 'N';
                        stk.push(new Pair(x-1, y));
                        stk.push(new Pair(x, y-1));
                        stk.push(new Pair(x, y+1));
                        stk.push(new Pair(x+1, y));
                    }
                }
            }
        }
        
        // mark all NON surrounded regions back to 'O' and render all surrounded regions
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == 'N') board[i][j] = 'O';
            }
        }
    }

  • 1
    M

    This is a very good, clear dfs solution using stacks to simulate recursion. Thank you for sharing. However, I have a question about stack overflow. If the space used by stacks here is similar to the space used by the call stack of recursion, why the call stack gives us an overflow, while using stacks don't? Thanks.


  • 0
    R

    thank you for your answer!


Log in to reply
 

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