Accepted dp solution in JAVA with detailed explaination.


  • 1
    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null||matrix.length == 0||matrix[0].length == 0)
                return 0;
            int height = matrix.length;
            int width = matrix[0].length;
               
            int[][] arr = new int[height][width];//create a same size int[][] to translate char into int for later use, and this makes this method run faster than that comparing characters.
            for(int row = 0 ; row < height; row++)
            {
                for(int col = 0 ; col < width; col++)
                {
                    arr[row][col] = matrix[row][col] - '0';
                }
            }
            int[][] dp = new int[height][width];//create same size dp[][] 
            boolean containsOne = false;//copy the first row and col into dp[][] and detect if there is a 1 in it;
            for(int row = 0 ; row < height; row++)
            {
                if(arr[row][0] == 1) containsOne = true;
                    dp[row][0] = arr[row][0];
            }
            for(int col = 0 ; col < width; col++)
            {
                if(arr[0][col] == 1) containsOne = true;
                    dp[0][col] = arr[0][col];
            }
            if(height == 1 || width == 1)
                return containsOne? 1 : 0;
            int res = containsOne?1:0;
    
            for(int row = 1 ; row < height; row++)
            {
                for(int col = 1 ; col < width; col++)
                {
                    if(arr[row][col] == 1)
                    {
                        int minAdj = Math.min(dp[row-1][col-1],Math.min(dp[row ][col-1],dp[row-1][col]));
    //dp[row][col] represents the size of square whose lower right corner is arr[row][col]
    //every position's value is 0 or square numbers like 1 4 9...
    // If the current position is 1, then the minimum value of the three adjacent positions dp[row-1][col-1],dp[row ][col-1] and dp[row-1][col] determines the square value of current position
    //sqrt(num) means the length of side of the square. if the new corner if going to be the lower right corner of a bigger square, the new area will be the 1 + 2*length + area of little square. You can understand this easily by drawing a matrix contains all 1s and map it into dp[][];
                        dp[row][col] = (int)Math.sqrt(minAdj)*2 + minAdj + 1;
                        res = Math.max(dp[row][col],res);
                        
                    }
                    
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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