Java beats 96% 8ms DP solution


  • 0
    S
    public int maximalSquare(char[][] matrix) {
         int h = matrix.length;
         if (h == 0) return 0;
         int w = matrix[0].length;
         int[][] dp = new int[h][w];
         int max = 0;
         for (int i = 0; i < h; i++) {
              for (int j = 0; j < w; j++) {
                   if (matrix[i][j] == '0') continue;
                   dp[i][j] = 1;
                   if (i-1>=0 && j-1>=0 && dp[i-1][j-1]>0){
                        int side = 0;
                        for (int k = 1; k <= dp[i-1][j-1]; k++) {
                             if (matrix[i][j-k] == '0' || matrix[i-k][j] == '0') break;
                             side++;
                        }
                        dp[i][j] += side;
                   }
                   max = Math.max(max, dp[i][j]);
              }
         }
         return max*max;
    }
    

Log in to reply
 

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