Easy understanding Java solution using Dynamic Programming


  • 0
    Y
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0)   return 0;
        int x = matrix.length; int y = matrix[0].length;
        int maxLength = 0;
        int[][] dp = new int[x][y];
        for(int i = 0; i < x; i++){
            dp[i][0] = matrix[i][0] - '0';
            if(dp[i][0] == 1) maxLength = 1;
        }  
        for(int i = 0; i < y; i++){
            dp[0][i] = matrix[0][i] - '0';
            if(dp[0][i] == 1) maxLength = 1;
        }  
        for(int i = 1; i < x; i++){
            for(int j = 1; j < y; j++){
                if(matrix[i][j] == '0') dp[i][j] = 0;
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength * maxLength;
    }

Log in to reply
 

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