<s> class Solution : <EOL> def maximalSquare ( self , matrix ) : <EOL> if not matrix : <EOL> return <NUM_LIT:0> <EOL> m , n = len ( matrix ) , len ( matrix [ <NUM_LIT:0> ] ) <EOL> size = [ [ <NUM_LIT:0> for j in xrange ( n ) ] for i in xrange ( <NUM_LIT:2> ) ] <EOL> max_size = <NUM_LIT:0> <EOL> for j in xrange ( n ) : <EOL> if matrix [ <NUM_LIT:0> ] [ j ] == '<STR_LIT:1>' : <EOL> size [ <NUM_LIT:0> ] [ j ] = <NUM_LIT:1> <EOL> max_size = max ( max_size , size [ <NUM_LIT:0> ] [ j ] ) <EOL> for i in xrange ( <NUM_LIT:1> , m ) : <EOL> if matrix [ i ] [ <NUM_LIT:0> ] == '<STR_LIT:1>' : <EOL> size [ i % <NUM_LIT:2> ] [ <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> else : <EOL> size [ i % <NUM_LIT:2> ] [ <NUM_LIT:0> ] = <NUM_LIT:0> <EOL> for j in xrange ( <NUM_LIT:1> , n ) : <EOL> if matrix [ i ] [ j ] == '<STR_LIT:1>' : <EOL> size [ i % <NUM_LIT:2> ] [ j ] = min ( size [ i % <NUM_LIT:2> ] [ j - <NUM_LIT:1> ] , size [ ( i - <NUM_LIT:1> ) % <NUM_LIT:2> ] [ j ] , size [ ( i - <NUM_LIT:1> ) % <NUM_LIT:2> ] [ j - <NUM_LIT:1> ] ) + <NUM_LIT:1> <EOL> max_size = max ( max_size , size [ i % <NUM_LIT:2> ] [ j ] ) <EOL> else : <EOL> size [ i % <NUM_LIT:2> ] [ j ] = <NUM_LIT:0> <EOL> return max_size * max_size <EOL> class Solution2 : <EOL> def maximalSquare ( self , matrix ) : <EOL> if not matrix : <EOL> return <NUM_LIT:0> <EOL> m , n = len ( matrix ) , len ( matrix [ <NUM_LIT:0> ] ) <EOL> size = [ [ <NUM_LIT:0> for j in xrange ( n ) ] for i in xrange ( m ) ] <EOL> max_size = <NUM_LIT:0> <EOL> for j in xrange ( n ) : <EOL> if matrix [ <NUM_LIT:0> ] [ j ] == '<STR_LIT:1>' : <EOL> size [ <NUM_LIT:0> ] [ j ] = <NUM_LIT:1> <EOL> max_size = max ( max_size , size [ <NUM_LIT:0> ] [ j ] ) <EOL> for i in xrange ( <NUM_LIT:1> , m ) : <EOL> if matrix [ i ] [ <NUM_LIT:0> ] == '<STR_LIT:1>' : <EOL> size [ i ] [ <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> else : <EOL> size [ i ] [ <NUM_LIT:0> ] = <NUM_LIT:0> <EOL> for j in xrange ( <NUM_LIT:1> , n ) : <EOL> if matrix [ i ] [ j ] == '<STR_LIT:1>' : <EOL> size [ i ] [ j ] = min ( size [ i ] [ j - <NUM_LIT:1> ] , size [ i - <NUM_LIT:1> ] [ j ] , size [ i - <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] ) + <NUM_LIT:1> <EOL> max_size = max ( max_size , size [ i ] [ j ] ) <EOL> else : <EOL> size [ i ] [ j ] = <NUM_LIT:0> <EOL> return max_size * max_size <EOL> class Solution3 : <EOL> def maximalSquare ( self , matrix ) : <EOL> if not matrix : <EOL> return <NUM_LIT:0> <EOL> H , W = <NUM_LIT:0> , <NUM_LIT:1> <EOL> table = [ [ [ <NUM_LIT:0> , <NUM_LIT:0> ] for j in xrange ( len ( matrix [ <NUM_LIT:0> ] ) ) ] for i in xrange ( len ( matrix ) ) ] <EOL> for i in reversed ( xrange ( len ( matrix ) ) ) : <EOL> for j in reversed ( xrange ( len ( matrix [ i ] ) ) ) : <EOL> if matrix [ i ] [ j ] == '<STR_LIT:1>' : <EOL> h , w = <NUM_LIT:1> , <NUM_LIT:1> <EOL> if i + <NUM_LIT:1> < len ( matrix ) : <EOL> h = table [ i + <NUM_LIT:1> ] [ j ] [ H ] + <NUM_LIT:1> <EOL> if j + <NUM_LIT:1> < len ( matrix [ i ] ) : <EOL> w = table [ i ] [ j + <NUM_LIT:1> ] [ W ] + <NUM_LIT:1> <EOL> table [ i ] [ j ] = [ h , w ] <EOL> s = [ [ <NUM_LIT:0> for j in xrange ( len ( matrix [ <NUM_LIT:0> ] ) ) ] for i in xrange ( len ( matrix ) ) ] <EOL> max_square_area = <NUM_LIT:0> <EOL> for i in reversed ( xrange ( len ( matrix ) ) ) : <EOL> for j in reversed ( xrange ( len ( matrix [ i ] ) ) ) : <EOL> side = min ( table [ i ] [ j ] [ H ] , table [ i ] [ j ] [ W ] ) <EOL> if matrix [ i ] [ j ] == '<STR_LIT:1>' : <EOL> if i + <NUM_LIT:1> < len ( matrix ) and j + <NUM_LIT:1> < len ( matrix [ i + <NUM_LIT:1> ] ) : <EOL> side = min ( s [ i + <NUM_LIT:1> ] [ j + <NUM_LIT:1> ] + <NUM_LIT:1> , side ) <EOL> s [ i ] [ j ] = side <EOL> max_square_area = max ( max_square_area , side * side ) <EOL> return max_square_area ; </s>
