Ac solution code


  • 0

    Example:

    1 0 1 0 0
    1 0 1 1 1
    1 1 1 1 1
    1 0 1 1 1 
    
    1 0 1 0 0
    1 0 1 1 1
    1 1 1 a b
    1 0 1 c d 
    

    The above 2 matrixes are the same, I just want to mark the nodes: a, b, c, d. (Char of these 4 nodes are all '1').

    maxEdge[i][j]: max square edge length with right-bottom vertex (i-1, j-1)(i=1..n, j=1..m)

    The max square edge length with right-bottom vertex d is determined by vertex a, b, c:

    Vertical edge vMax(d) is determined by: min(maxEdge(a), maxEdge(b))
    Horizon  edge hMax(d) is determined by: min(maxEdge(a), maxEdge(c))
    
      maxEdge of square(d) 
    = min(vMax(d), hMax(d))  
    = min(maxEdge(a), maxEdge(b), maxEdge(a), maxEdge(c)) 
    = min(maxEdge(a), maxEdge(b), maxEdge(c))    
    

    JAVA Code: Runtime = O(nm); Space = O(nm)

    public int maximalSquare(char[][] A) {
        if (A == null || A.length == 0) return 0;
        int n = A.length, m = A[0].length, max = 0;
        int maxEdge[][] = new int[n + 1][m + 1];// maxEdge[i][j]: max square edge length with right-bottom vertex (i-1, j-1)(i=1..n, j=1..m)
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A[i-1][j-1] == '1') {//  Choose the minimum square with right-bottom vertex (i-1, j-1)
                    maxEdge[i][j] = Math.min(maxEdge[i-1][j], Math.min(maxEdge[i][j-1], maxEdge[i-1][j-1])) + 1;
                    max = Math.max(max, maxEdge[i][j]);
                }
            }
        }
        return max * max;
    }

Log in to reply
 

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