Java O(N^2) DP Solution


  • 0
    M
    class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
            final int M = matrix.length, N = matrix[0].length;
            int maxLen = 0;
            for(int i=0; i<M; i++) {
                if(matrix[i][0]!='0'){
                    maxLen=1;
                    break;
                }
            }
            if(maxLen==0){
                for(int j=1; j<N; j++) {
                    if(matrix[0][j]!='0'){
                        maxLen=1;
                        break;
                    }
                }
            }
            for(int i=1; i<M; i++){
                for(int j=1; j<N; j++){
                    if(matrix[i][j]!='0'){
                        int cur = 1 + Math.min(matrix[i-1][j-1], Math.min(matrix[i-1][j], matrix[i][j-1]));
                        matrix[i][j] = (char)cur;
                        maxLen = Math.max(maxLen, cur-'0');
                    }
                }
            }
            return maxLen*maxLen;
        }
    }
    

Log in to reply
 

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