Sharing my 12ms C++ solution


  • 1
    T
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int m = matrix.size();
            if(m==0)
                return 0;
            int n = matrix[0].size();
            if(n==0)
                return 0;
                
            vector<vector<int>> DP;
            DP.resize(m+1);
            int i, j;
            for(i=0; i<=m; i++)
                DP[i].resize(n+1, 0);
                
            int resLen=0;
            for(i=1; i<=m; i++)
                for(j=1; j<=n; j++)
                {
                    if(matrix[i-1][j-1]=='0')
                        DP[i][j] = 0;
                    else
                    {
                        int minimum = INT_MAX;
                        minimum = min(minimum, DP[i-1][j-1]);
                        minimum = min(minimum, DP[i-1][j]);
                        minimum = min(minimum, DP[i][j-1]);
                        DP[i][j]=1+minimum;
                        resLen = max(resLen, DP[i][j]);
                    }
                }
                
            int result = resLen*resLen;
            return result;
        }
    };

Log in to reply
 

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