My cpp solution which is easy to understand.


  • 0
    H
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int matrixRowSize=matrix.size();
            if(!matrixRowSize)
                return 0;
            int matrixColSize=matrix[0].size();
            int dp[1000][1000]={0};
            int max=0;
            for(int i=0;i<matrixRowSize;i++)
            {
                dp[i][0]=matrix[i][0]-'0';
                if(dp[i][0]>max)
                    max=dp[i][0];
            }
            for(int i=0;i<matrixColSize;i++)
            {
                dp[0][i]=matrix[0][i]-'0';
                if(dp[0][i]>max)
                    max=dp[0][i];
            }
            for(int i=1;i<matrixRowSize;i++)
            {
                for(int j=1;j<matrixColSize;j++)
                {
                    if(matrix[i][j]=='1'){
                    dp[i][j]=INT_MAX;
                    if(dp[i-1][j]+1<dp[i][j])
                        dp[i][j]=dp[i-1][j]+1;
                    if(dp[i][j-1]+1<dp[i][j])
                        dp[i][j]=dp[i][j-1]+1;
                    if(dp[i-1][j-1]+1<dp[i][j])
                        dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>max)
                        max=dp[i][j];
                    }
                    else{
                        dp[i][j]=0;
                    }
                }
            }
            return max*max;
        }
    };
    

Log in to reply
 

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