13ms java DP beats 68%


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

Log in to reply
 

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