Maximum Square -- LeetCode 221

[Question]

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

[Analysis]
This is similar with the Maximum Rectangle problem. While it can be done by the same approach, there is a  Dynamic Programming solution to solve this.

Define S[i,j] = the length of largest square positioned at Matrix[i,j], then
          S[i,0] = 1 if Matrix[i,0]= '1';
          S[0,j] = 1 if Matrix[0,j]= '1';
          S[i,j] = min ( S[i-1,j-1], S[i-1,j], S[i,j-1] ) + 1 if Matrix[i,j]='1', i>0, j>0;

Time complexity and space complexity are O(M x N).

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

};