# Share my C++ solution,easy to understand

• ``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int row = matrix.size();
if (row == 0)
return 0;
int col = matrix[0].size();
if (col == 0)
return 0;

int max_len = 0;
vector<vector<int>> dp(row, vector<int>(col, 0));

for (int i = 0; i < col; i++)
{
if (matrix[0][i] == '1')
{
dp[0][i] = 1;
max_len = 1;
}
}

for (int i = 0; i < row; i++)
{
if (matrix[i][0] == '1')
{
dp[i][0] = 1;
max_len = 1;
}
}

for (int i = 1; i < row; i++)
{
for (int j = 1; j < col;j++)
{
if (matrix[i][j] == '0')
continue;

dp[i][j] = min(dp[i][j-1], dp[i-1][j]);
dp[i][j] = min(dp[i][j], dp[i-1][j-1]) + 1;

max_len = max(max_len, dp[i][j]);
}
}

return max_len * max_len;
}
};``````

• Optimization in Space Complexity:

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int row = matrix.size();
if (row == 0)
return 0;
int col = matrix[0].size();
if (col == 0)
return 0;

int max_len = 0;
vector<int> dp1(col, 0);
vector<int> dp2(col, 0);

for (int i = 0; i < col; i++)
{
if (matrix[0][i] == '1')
{
dp1[i] = 1;
max_len = 1;
}
}

for (int i = 1; i < row; i++)
{
dp2[0] = matrix[i][0] - '0';
max_len = max(max_len, dp2[0]);

for (int j = 1; j < col;j++)
{
if (matrix[i][j] == '0')
continue;

dp2[j] = min(dp1[j-1], dp1[j]);
dp2[j] = min(dp2[j], dp2[j-1]) + 1;

max_len = max(max_len, dp2[j]);
}

for (int k = 0; k < col; k++)
{
dp1[k] = dp2[k];
dp2[k] = 0;
}
}

return max_len * max_len;
}
};``````

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