LeetCode Solutions
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n));
int maxLength = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0 || matrix[i][j] == '0')
dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
maxLength = max(maxLength, dp[i][j]);
}
return maxLength * maxLength;
}
};
|
class Solution {
public int maximalSquare(char[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
int[][] dp = new int[m][n];
int maxLength = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0 || matrix[i][j] == '0')
dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
return maxLength * maxLength;
}
}
|
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
maxLength = 0
for i in range(m):
for j in range(n):
if i == 0 or j == 0 or matrix[i][j] == '0':
dp[i][j] = 1 if matrix[i][j] == '1' else 0
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1]
[j], dp[i][j - 1]) + 1
maxLength = max(maxLength, dp[i][j])
return maxLength * maxLength
|
