Share my clear and concise JAVA DFS solution


  • 1
    Y

    Note that if an 'O' is not surrounded by 'X', then this 'O' must at the edge of the board or has connected with an edge_board_O, so what we need to do is to find ALL 'O's in this kind and mark them. So I ues DFS to find them and mark them as 'M'.

    In the DFS_Edge_O_Marking function, I put the if statement e.g. if(i-1>0) to reduce the recrusion times in case of stack over flow.

    public class Solution {
        public void solve(char[][] board) {
            if(board==null) return;
            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){DFS_Edge_O_Marking(board,i,j);
                    }
                }
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++){
                    if(board[i][j]=='M') board[i][j]='O';
                    else board[i][j]='X';
                }
            return;
            
        }
        
        public void DFS_Edge_O_Marking(char[][] board,int i,int j) {
            if(i<0||j<0||i>=board.length||j>=board[0].length) return;
            if(board[i][j]=='M'||board[i][j]=='X') return;
            board[i][j]='M';
            if(i-1>0) DFS_Edge_O_Marking(board,i-1,j);//put a if statement in case of stack over flow;
            if(i+1<board.length) DFS_Edge_O_Marking(board,i+1,j);
            if(j-1>0) DFS_Edge_O_Marking(board,i,j-1);
            if(j+1<board[0].length) DFS_Edge_O_Marking(board,i,j+1);
        }
    }
    

Log in to reply
 

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