My java solution use dp


  • 0
    M
    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] dp = new int[row][col];
            int max = 0;
            for(int i = 0 ; i < row ; i++){
                if(matrix[i][0] == '1'){
                    dp[i][0] = 1;
                    max= Math.max(max,dp[i][0]);
                }
            }
            for(int i = 0 ; i < col ; i++){
                if(matrix[0][i] == '1'){
                   dp[0][i] = 1; 
                   max = Math.max(max,dp[0][i]);
                }
            }
            for(int i = 1 ; i < row ; i++){
                for(int j = 1 ; j < col ; j++){
                    if(matrix[i][j] == '1'){
                        if(matrix[i-1][j-1] == '1' && matrix[i][j-1] == '1' && matrix[i-1][j] == '1'){
                            int len = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]);
                            dp[i][j] = len + 1;
                        }else{
                            dp[i][j] = 1;
                        }
                        max= Math.max(max,dp[i][j]*dp[i][j]);
                    }
                }
            }
            return max;
        }
    }

Log in to reply
 

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