LeetCode 221 Maximal Square

思路

dp解法。dp[i][j]表示以(i, j)为右下角的正方形的最大边长；
状态转移方程：dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1；
初始状态：i == 0 || j == 0, dp[i][j] = matrix[i][j].

复杂度

时间复杂度O(n*m) = O(n^2)

空间复杂度O(n*m) = O(n^2)

代码

class Solution {
    public int maximalSquare(char[][] matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) {
    return 0;}int n = matrix.length;int m = matrix[0].length;int[][] dp = new int[n][m];int max = 0;for (int i = 0; i < m; i++) {
    dp[0][i] = matrix[0][i] - '0';if (dp[0][i] > max) {
    max = dp[0][i];}}for (int i = 0; i < n; i++) {
    dp[i][0] = matrix[i][0] - '0';if (dp[i][0] > max) {
    max = dp[i][0];}}for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
    if (matrix[i][j] == '0') {
    dp[i][j] = 0;} else {
    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;}if (dp[i][j] > max) {
    max = dp[i][j];}}}return max * max;}
}