DP+ BFS solution o(n)?


  • 4
    S
    public class Solution {
        int length =0;
        int height = 0;
        
        public void solve(char[][] board) {
            if(board == null || board.length ==0){
                return;
            }
            
            length = board[0].length;
            height = board.length;
            char[][] copy = new char[height][length];
            
            for(int i=0; i< height;i++){
               copyCharToCopy(board, copy, i, 0);
               copyCharToCopy(board, copy, i, length-1);
            }
            
            for(int j=0; j<length; j++){
                copyCharToCopy(board, copy, 0, j); 
                copyCharToCopy(board, copy, height-1, j);
            }
            
            for(int i=0; i<height;i++){
                for(int j=0;j<length;j++){
                    if(board[i][j] =='O' && copy[i][j] != 'O'){
                        board[i][j] = 'X';
                    }
                }
            }
            
            return;
        }
        
        private void copyCharToCopy(char[][] board, char[][] copy, int h, int w){
        	
        	Stack<Integer> iS = new Stack<Integer>();
        	Stack<Integer> jS =new Stack<Integer>();
        	iS.push(h);
        	jS.push(w);
        	
        	while(!iS.isEmpty()){
        		int i = iS.pop();
        		int j = jS.pop();
        		if(!(i<0 || i>= height || j<0 || j>= length || copy[i][j] == 'O' || board[i][j] =='X')){
    	    		copy[i][j] = board[i][j];
    	    		iS.push(i-1);
    	    		jS.push(j);
    	    		
    	    		iS.push(i+1);
    	    		jS.push(j);
    	    		
    	    		iS.push(i);
    	    		jS.push(j-1);
    	    		
    	    		iS.push(i);
    	    		jS.push(j+1);
        		}
        	}
        }
    }
    

    use copy to store if the point is connected to edge, every point should be visited just once since we do not visit the point if it is visited


  • 0
    P

    Very beautiful code! However, I think this is based on DFS, not BFS. It pushes all neighbors into stack, and pick the top one, which is one of the neighbors just pushed in, and further gets its neighbors.

    Another thought I have is probably we can use mark it a third symbol such as 'A' for the 'O's which are indeed going to be left (which are the 'O's in your copy[][]). Finally change all 'O's into 'X' and change 'A' into 'O'. This may use less space.


  • 0
    L

    That's right!


Log in to reply
 

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