A Brute Force Solution Not That Heavy!


  • 1
    H

    I saw almost all posts are about DP. So I try to post a Brute Force solution here. And this solution works pretty well, cause it GIVES UP quickly in some condition. 13ms

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            int result = 0;
            if (matrix.length == 0) { return result; }
            int height = matrix.length, width = matrix[0].length;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    int maxPossibleHeight = height -i;
                    if (maxPossibleHeight <= result) { return result * result; } // GIVE UP
                    int maxPossibleWidth = width - j;
                    if (maxPossibleWidth <= result) { break; } // GIVE UP
                    int range = Math.min(maxPossibleHeight,maxPossibleWidth);
                    result = Math.max(result,checkSquare(matrix,i,j,range));
                }
            }
            return result * result;
        }
        public int checkSquare(char[][] matrix, int x, int y, int range) {
            int result = 0;
            for (int i = 0; i < range; i++) {
                for (int j = x + i, k = y; k <= y + i; k++) { if (matrix[j][k] == '0') { return result; } } // GIVE UP
                for (int j = y + i, k = x; k <= x + i; k++) { if (matrix[k][j] == '0') { return result; } } // GIVE UP
                result++;
            }
            return result;
        }
    }

Log in to reply
 

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