Sharing my 6ms c++ solution. Reasonable pruning.


  • 0
    L
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            if (matrix.size()==0 || matrix[0].size()==0)
                return 0;
            int width = matrix[0].size();
            int rec[width];
            for (int i=0; i<width; i++)
                rec[i] = 0;
            int max_len = 0;
            for (int i=0; i<matrix.size(); i++)
            {
                int r_len = 0;
                for (int j=0; j<matrix[i].size(); j++)
                {
                    if (matrix[i][j] == '1')
                    {
                        rec[j]++;
                        r_len++;
                    }
                    else
                    {
                        rec[j] = 0;
                        r_len = 0;
                    }
                    if (rec[j] > max_len && r_len > max_len)
                    {
                        int c_min = rec[j];
                        for (int k=j; k>=0 && rec[k]>max_len; k--)
                        {
                            if (rec[k] < c_min)
                            {
                                c_min = rec[k];
                            }
                            int r_max = min(c_min, j-k+1);
                            if (r_max > max_len)
                            {
                                max_len = r_max;
                            }
                        }
                    }
                }
            }
            return max_len*max_len;
        }
    };
    

Log in to reply
 

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