c++ solution


  • 0
    B
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            if(!matrix.size()) return 0;
            int m=matrix[0].size(),n=matrix.size();
            int result=0;
            vector<vector<int>> dp(n,(vector<int> (m,0)));
            //initialize 
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++){
                    dp[i][j]=matrix[i][j]-'0';
                    result=max(result,dp[i][j]);
                }
            //could memorized search with O(n) space to save space
            for(int i=1;i<n;i++){
                for(int j=1;j<m;j++){
                    if(matrix[i][j]=='1')
                        dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) +1;
                    result=max(result,dp[i][j]);
                }
            }
            return result*result;
            
        }
    };
    

Log in to reply
 

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