LC 0221 [M] Maximal Square - ALawliet/algorithms GitHub Wiki

https://leetcode.com/problems/maximal-square/discuss/600149/Python-Thinking-Process-Diagrams-DP-Approach

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # if matrix is None or len(matrix) < 1:
            # return 0
        
        ROWS = len(matrix)
        COLS = len(matrix[0])
        
        T = [[0]*(COLS+1) for _ in range(ROWS+1)]
        max_side = 0
        
        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == '1':
                    UL = T[r][c] # ^<
                    L = T[r+1][c] # <
                    U = T[r][c+1] # ^
                    T[r+1][c+1] = min(UL, L, U) + 1 # Be careful of the indexing since dp grid has additional row and column
                    max_side = max(max_side, T[r+1][c+1])
                
        return max_side * max_side