Stackoverflow Error when running the last longest test


  • 0
    L

    Basic idea:

    • Step 1: find 'O' on the edge of the board as one possible entry, which may result in that any other 'O' that connects with this entry should not be flipped.
    • Step 2: for each entry point, set visited matrix related value as 1 and do depth-first search recursively to find the other points that connects with this entry point.
    • Step 3: after the DFS search, for all the points whose related value in visited matrix is still 0, we set the value in board to 'X'.

    My code example:

    public class Solution {
        public void solve(char[][] board) {
            if(board == null || board.length == 0){
                return;
            }
            
            int[][] visited = new int[board.length][board[0].length];
            
            for(int i = 0; i < board[0].length - 1; i++){
                if(board[0][i] == 'O' && visited[0][i] == 0){
                    DFS(board, 0, i, visited);
                }
            }
            
            for(int i = 0; i < board.length - 1; i++){
                if(board[i][board[0].length - 1] == 'O' && visited[i][board[0].length - 1] == 0){
                    DFS(board, i, board[0].length - 1, visited);
                }
            }
            
            for(int i = board[0].length - 1; i >= 1; i--){
                if(board[board.length - 1][i] == 'O' && visited[board.length - 1][i] == 0){
                    DFS(board, board.length - 1, i, visited);
                }
            }
            
            for(int i = board.length - 1; i >= 1; i--){
                if(board[i][0] == 'O' && visited[i][0] == 0){
                    DFS(board, i, 0, visited);
                }
            }
            
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[0].length; j++){
                    if(visited[i][j] == 0){
                        board[i][j] = 'X';
                    }
                }
            }
        }
        
        public void DFS(char[][] board, int x, int y, int[][] visited){
            visited[x][y] = 1;
            
            int[] dx = new int[]{-1, 1, 0, 0};
            int[] dy = new int[]{0, 0, -1, 1};
            
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length){
                    if(board[nx][ny] == 'O' && visited[nx][ny] == 0){
                        DFS(board, nx, ny, visited);
                    }
                }
            }
        }
    }
    

    I think the basic idea of this algorithm is simple and easy to understand. However, this implementation will fail when the input is quite huge. Can someone help me to find the bug? Thanks!

    Best wishes.

    Tony


Log in to reply
 

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