Simple Dynamic Programming Solution in O(NM)


  • 1
    S
    class Matrix
    {
    private:
    
        const vector<vector<char>> &mat;
        const int _rows;
        const int _cols;
    
    public:
    
        Matrix(const vector<vector<char>> &m)
            : mat(m)
            , _rows(m.size())
            , _cols(m[0].size())
        {
        }
    
        int rows() const { return _rows; }
        int cols() const { return _cols; }
    
        char get(int x, int y) const { return mat[y][x]; }
    
        int maximal_square() const
        {
            int max_square = 0;
            
            // dp[y][x] = maximal square's side length whose bottom-right corner is on (x,y)
            vector<vector<int>> dp( rows(),
                                    vector<int>(cols(), 0) );
    
            // the base cases: for each cell on the topmost row and leftmost column,
            // they can only be the bottom-right corner of a 1-sided square, if at all
            for (int c = 0; c < cols(); ++c)
            {
                dp[0][c] = get(c, 0) == '1' ? 1 : 0;
                max_square = max(max_square, dp[0][c]);
            }
            for (int r = 0; r < rows(); ++r)
            {
                dp[r][0] = get(0, r) == '1' ? 1 : 0;
                max_square = max(max_square, dp[r][0]);
            }
    
            // for the rest, a cell can be the bottom-right corner of a k+1 sided square, IFF
            // (a) it contains a '1',
            // (b) its top, left, and top-left neighbors all contain '1's, AND
            // (c) k is the minimum dp value of those neighbors
            // otherwise, this cell is at best the bottom-right corner of its own 1-sided square
    
            for (int y = 1; y < rows(); ++y)
            {
                for (int x = 1; x < cols(); ++x)
                {
                    if (get(x, y) != '1')
                    {
                        dp[y][x] = 0;
                    }
                    else
                    {
                        dp[y][x] = 1;
                        if (get(x-1, y-1) == '1' &&
                            get(x-1, y)   == '1' &&
                            get(x, y-1)   == '1')
                        {
                            dp[y][x] += min( dp[y-1][x-1], min(
                                             dp[y][x-1],
                                             dp[y-1][x] ));
                        }
                        
                        max_square = max(max_square, dp[y][x]);
                    }
                }
            }
    
            return max_square * max_square;
        }
    
    };
    
    
    class Solution {
    public:
    
        int maximalSquare(vector<vector<char>>& matrix) {
            if (matrix.size() == 0) return 0;
            
            Matrix mat(matrix);
            return mat.maximal_square();
        }
    
    };

Log in to reply
 

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