My DP Solution with less than 11 ms


  • 0
    B
    public int maximalSquare(char[][] matrix) {
    	if (matrix.length == 0) {
    		return 0;
    	}
    	int[][] dp = new int[matrix.length][matrix[0].length];
    	int result = 0;
    	int lastX;
    	int lastY;
    	for (int i = 0; i < matrix.length; i++) {
    		for (int j = 0; j < matrix[0].length; j++) {
    			// when come to 0,failed
    			if (matrix[i][j] != '1') {
    				continue;
    			}
    			// affirm the bordern element right
    			if (i == 0 || j == 0) {
    				dp[i][j] = 1;
    				result = Math.max(dp[i][j], result);
    				continue;
    			}
    
    			// the father matrix row and table number
    			lastX = i - 1;
    			lastY = j - 1;
    
    			if (matrix[lastX][lastY] != '1') {
    				dp[i][j] = Math.max(1, dp[i][j]);
    				continue;
    			}
    			int count = 1;
    			// search the large matrix at i,j
    			for (; count <= dp[lastX][lastY]; count++) {
    				if (matrix[i][j - count] != '1' || matrix[i - count][j] != '1') {
    					break;
    				}
    			}
    			// count less than the father node,don't need to update the num
    			if (count <= dp[lastX][lastY]) {
    				dp[i][j] = Math.max(count, dp[i][j]);
    				continue;
    			}
    			// update the node state
    			if (dp[i - 1][j - 1] + 1 > dp[i][j]) {
    				dp[i][j] = dp[i - 1][j - 1] + 1;
    				result = Math.max(dp[i][j], result);
    			}
    		}
    	}
    	return result * result;
    }

Log in to reply
 

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