Java DFS, Avoided TLE, Readable


  • 2
    J

    Is there anyone knows what is the space complexity for BFS and DFS solutions for this question? when there are recursive calls and stacks involved, I don't understand how the program actually executed. Thank you!

    public class Solution {
        public void solve(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++){
                    if ((i == 0 || i == board.length-1 || j == 0 || j == board[i].length-1) && (board[i][j] == 'O')){
                    dfs(i, j, board);
                    }
                }
            }
            for(int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    else if (board[i][j] == 'M') {
                        board[i][j] = 'O';
                    }       
                }
            }
        }
        
        public void dfs(int i, int j, char[][] board){
            if ((i >= 0 && i < board.length && j >= 0 && j < board[i].length) && (board[i][j] == 'O')){
                board[i][j] = 'M';
                // the next four lines are cases where the cell is at the edge, 
                // in these cases we only need to check one direction, 
                // "in-bound" direction, to avoid unnecessary calls to dfs()
                if(i == 0) dfs(i+1, j, board);
                else if (j == 0) dfs(i, j+1, board);
                else if(i == board.length-1) dfs(i-1, j, board);
                else if(j == board[i].length-1) dfs(i, j-1, board);
                else{
                dfs(i-1, j, board);
                dfs(i+1, j, board);
                dfs(i, j-1, board);
                dfs(i, j+1, board);                
                }
            }
        }
    }
    

  • 0

    @Jingshi Actually your four lines is logically unnecessary but actually necessary in this problem which is confusing for long. @StefanPochmann Why cannot we traverse the edge again since it's labelled?

    B.T.W. the time complexity here should be O(n^2) since all the traverser does is traversing all the cells once.

    Actually what I want in this problem is something more like this.

    public class Solution {
        public void solve(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++){
                    if ((i == 0 || i == board.length-1 || j == 0 || j == board[i].length-1) && (board[i][j] == 'O')){
                    dfs(i, j, board);
                    }
                }
            }
            for(int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] == 'M') board[i][j] = 'O';
                    else board[i][j] = 'X';
                }
            }
        }
        
        public void dfs(int i, int j, char[][] board){
            if(i < 0 || i > board.length-1 || j < 0 || j > board[i].length-1 || board[i][j] == 'M') return ;
            board[i][j] = 'M';
            dfs(i-1, j, board);
            dfs(i+1, j, board);
            dfs(i, j-1, board);
            dfs(i, j+1, board);
        }
    }
    

    But as expected, it's just RE...Confusing me for long.


  • 0
    J
    This post is deleted!

  • 0

    @LHearen said in Java DFS, Avoided TLE, Readable:

    @StefanPochmann Why cannot we traverse the edge again since it's labelled?

    Huh? If you mean why @Jingshi's solution gets accepted while yours crashes with StackOverflowError, then look at the input you fail. And think about why your solution fails that input. And why @Jingshi's solution doesn't fail it. And why @Jingshi's solution doesn't avoid the issue in general, but just adapts to the specific test case in the OJ's test suite so we can easily make it fail by modifying that test case slightly.


Log in to reply
 

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