Share my straight forward brute force solution


  • 0
    O
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int N = matrix.size();
            if (N <= 0) return 0;
            int M = matrix[0].size();
            vector<vector<int> > sum(N + 1, vector<int>(M + 1, 0));
            for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1] - '0';
            }
            for (int len = min(N, M) - 1; len >= 0; len--) {
                for (int i = 1; i <= N; i++) {
                    if (i + len > N) break;
                    for (int j = 1; j <= M; j++) {
                        if (j + len > M) break;
                        int val = sum[i + len][j + len] - sum[i + len][j - 1] - sum[i - 1][j + len] + sum[i - 1][j - 1];
                        if (val == (len + 1) * (len + 1)) return val;
                    }
                }
            }
            return 0;
        }
    };

Log in to reply
 

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