BiruLyu
7/8/2017 - 5:17 PM

221. Maximal Square(O(n) space).cpp

``````public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
// dp(i, j) represents the length of the square whose lower-right corner is located at (i, j)
// dp(i, j) = min{ dp(i-1, j-1), dp(i-1, j), dp(i, j-1) }
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '0') continue;

dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
res = Math.max(res, dp[i][j]);
}
}
return res * res;
}
}``````
``````int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(m + 1, 0);
int maxsize = 0, pre = 0;
for (int j = 0; j < n; j++) {
for (int i = 1; i <= m; i++) {
int temp = dp[i];
if (matrix[i - 1][j] == '1') {
dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1;
maxsize = max(maxsize, dp[i]);
}
else dp[i] = 0;
pre = temp;
}
}
return maxsize * maxsize;
}``````