Java Solution DP


  • 0
    Z

    The key point is to understand that minimum of neighboring squares (matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) is the one, that is going to be expanded at current iteration. You can prove if by yourselves

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix.length == 0) return 0;
            int a[][] = new int[matrix.length][matrix[0].length];
            int area = 0;
            for( int i = 0;i<matrix.length;i++){
                a[i][0] = matrix[i][0]-'0';
                area = Math.max(area, a[i][0]);
            }
            for( int i = 0;i<matrix[0].length;i++){
                a[0][i] = matrix[0][i]-'0';
                area = Math.max(area, a[0][i]);
            }
            for(int i = 1;i<matrix.length;i++){
                for(int j  = 1;j<matrix[i].length;j++){
                    int up = a[i-1][j], back = a[i][j-1], d = a[i-1][j-1], self = matrix[i][j]-'0';
                    if(up == 0 || back == 0 || d == 0 || self == 0) a[i][j] = matrix[i][j]-'0';
                    else {
                      int min = Math.min(Math.min(up, back),d);
                      int sqrt = (int)Math.sqrt(min)+1;
                      a[i][j] = sqrt*sqrt;
                      area = Math.max(area, a[i][j]);
                    }
                }
                
            }
            // print(a);
            return area;
        }
        
        public void print(int a[][]){
            for(int i = 0;i<a.length;i++){
                for(int j  = 0;j<a[i].length;j++){
                    System.out.print(a[i][j]+" ");
                    
                }
                System.out.println();
            }
        }
    }

Log in to reply
 

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