Concise DP solution C++ 6ms


  • 1
    J
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int m=matrix.size();
            int n=m==0?0:matrix[0].size();
            int side=0;
            for(int i=0; i<m; i++)
            {
                for(int j=0; j<n; j++)
                {
                    if(matrix[i][j]=='0')
                        continue;
                    matrix[i][j]=min(i>0?matrix[i-1][j]:'0', min(j>0?matrix[i][j-1]:'0', i>0&&j>0?matrix[i-1][j-1]:'0'))+1;
                    side=max(side, matrix[i][j]-'0');
                }
            }
            return side*side;
        }
    };
    

Log in to reply
 

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