Share my standard dp solution [Java]


  • 0
    M
    /*
        size[i][j] -- size of maximal square whose bottom-right point is (i, j)
        if matrix[i][j] == 0, size[i][j] = 0;
        if matrix[i][j] == 1, size[i][j] = 1 + min(size[i-1][j-1], size[i-1][j], size[i][j-1]).
    */
    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if (matrix.length == 0) {
                return 0;
            }
            int[] prev = new int[matrix[0].length], cur = new int[matrix[0].length];
            int max = 0;
            for (int i = 0; i < matrix.length; ++i) {
                for (int j = 0; j < matrix[0].length; ++j) {
                    if (matrix[i][j] == '0') {
                        cur[j] = 0;
                    } else {
                        int up = i - 1 < 0 ? 0 : prev[j];
                        int left = j - 1 < 0 ? 0 : cur[j - 1];
                        int upLeft = i - 1 < 0 || j - 1 < 0 ? 0 : prev[j - 1];
                        cur[j] = 1 + Math.min(Math.min(up, left), upLeft);
                        max = Math.max(cur[j], max);
                    }
                }
                int[] temp = prev;
                prev = cur;
                cur = temp;
            }
            return max * max;
        }
    }

Log in to reply
 

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