Easy Understand Strightforward Java DP Solution with Explanation


  • 0
    M

    The basic idea is to build a boolean matrix initialized with false, which means all points are not connected to open. And then scan the board, once an 'O' is found, check whether it is on the boarder, if so, change its boolean value to be true, if not, check its surroundings, if any of them is true, it's true. Keep scanning and updating the DP matrix first from left-top then from right-bottom. Mostly, one pair of scans is enough, but actually some special cases need a second pair. So, define a boolean variable to check whether a change is made or not in the scan. If none change, break and our DP matrix is correctly built.
    After that, scan the board, when come across an 'O', check the DP matrix, if it says false, change it to 'X';

    public void solve(char[][] board) {
    
    	int height = board.length;
    	if (height < 1)
    		return;
    
    	int width = board[0].length;
    
    	boolean[][] dp = new boolean[height][width];
    
        //Start scanning twice as one pair
    	while (true) {
    		boolean changed = false;
    
           //Scan from top-left
    		for (int i = 0; i < height; i++)
    			for (int j = 0; j < width; j++) {
    				if (board[i][j] == 'O') {
    					boolean temp = dp[i][j];
    					dp[i][j] = dp[i][j] || i == 0 || i == height - 1
    							|| j == 0 || j == width - 1 || dp[i - 1][j]
    							|| dp[i][j - 1] || dp[i + 1][j] || dp[i][j + 1];
    
    					changed = changed || !(temp == dp[i][j]);
    				}
    			}
    
            //Scan from bottom-right
    		for (int i = height - 1; i >= 0; i--)
    			for (int j = width - 1; j >= 0; j--) {
    				if (board[i][j] == 'O') {
    					boolean temp = dp[i][j];
    					dp[i][j] = dp[i][j] || i == 0 || i == height - 1
    							|| j == 0 || j == width - 1 || dp[i - 1][j]
    							|| dp[i][j - 1] || dp[i + 1][j] || dp[i][j + 1];
    					changed = changed || !(temp == dp[i][j]);
    				}
    			}
    
           ///DP matrix is done!
    		if (!changed)
    			break;
    	}
    
    
    //Change O to X according to DP matrix
    	for (int i = height - 1; i >= 0; i--)
    		for (int j = width - 1; j >= 0; j--) 
    			if (board[i][j] == 'O' && dp[i][j] == false) 
    				board[i][j] = 'X';
    			
    		
    
    }

Log in to reply
 

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