JAVA, DP, 372MS


  • 0
    W

    public class Solution {

    public int maximalSquare(char[][] matrix) {
        int res = 0;
        if(matrix.length == 0){
        	return res;
        }
        
        int[][] opt = new int[matrix.length][matrix[0].length];
        
       //initialize the optimal matrix
    
        for(int i=0; i<matrix.length; i++){
        	if(matrix[i][0] == '1'){
        		opt[i][0] = 1;
        		res = 1;
        	}
        	else{
        		opt[i][0] = 0;
        	}
        }
        
        for(int i=0; i<matrix[0].length; i++){
        	if(matrix[0][i] == '1'){
        		opt[0][i] = 1;
        		res = 1;
        	}
        	else{
        		opt[0][i] = 0;
        	}
        }
    
       //use to dp to calculate the length of the square
        
        for(int i=1; i<matrix.length; i++){
        	for(int j=1; j<matrix[0].length; j++){
        		if(matrix[i][j] == '0'){
        			opt[i][j] = 0;
        		}
        		else if(opt[i-1][j] == 0 || opt[i][j-1] == 0){
        			opt[i][j] = 1;
        		}
        		else{
        			int sub = Math.min(opt[i-1][j], opt[i][j-1]);
        			if(matrix[i-sub][j-sub] == '1'){
        				opt[i][j] = sub + 1;
        			}
        			else{
        				opt[i][j] = sub;
        			}
        		}
        		res = Math.max(res, opt[i][j]);
        	}
        }
        
        return res * res;
    }
    

    }


Log in to reply
 

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