221. Maximal Square

https://leetcode.com/problems/maximal-square/

Maximal Square - LeetCode

Solution

class Solution:
    def maximalSquare(self, matrix):        
        ROW, COL = len(matrix), len(matrix[0])
        ans = 0
        for i in range(COL):
            matrix[0][i] = 1 if matrix[0][i]=='1' else 0
            ans |= matrix[0][i]
        for i in range(1, ROW):
            matrix[i][0] = 1 if matrix[i][0]=='1' else 0            
            ans |= matrix[i][0]

        for r in range(1, ROW):
            for c in range(1, COL):
                if matrix[r][c] == '0':
                    matrix[r][c] = 0
                    continue
                if ans == 0:
                    ans = 1
                
                if matrix[r-1][c] and matrix[r][c-1] and matrix[r-1][c-1]:
                    num = min(matrix[r-1][c], matrix[r][c-1], matrix[r-1][c-1]) + 1
                    matrix[r][c] = num
                    ans = max(ans, num)
                else:
                    matrix[r][c] = 1
        return ans**2

• 첫 행과 첫 열의 문자열을 숫자로 바꿔준다.
• or 연산을 활용해서 하나라도 1이 있으면 ans를 1로 바꿔준다.
• (1,1) 부터 시작해서 0이 나오면 숫자 0을 넣어주고 패쓰한다.
• ans가 아직도 0이라면 matrix 값이 1일 때 ans에 1을 넣어준다.
• 위, 왼쪽, 왼쪽 위를 모두 살펴서 모두 0이 아니면 더 큰 정사각형을 만들 수 있다.
  
  • 3곳 중 가장 작은 값을 가져오고 +1해서 정사각형의 사이즈를 하나 키워준다.
  • 해당 matrix의 값을 num으로 대입하고, ans도 더 큰 값을 넣는다.
• 위, 왼쪽, 왼쪽 위 중 하나라도 0이 있으면 matrix에는 1을 넣어준다.
• 마지막엔 정사각형의 넓이를 반환해야하므로 제곱해준다.
• 시간 복잡도 공간 복잡도 모두 O(mn)으로 효율적으로 해결하였다.

Another

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        ROW = len(matrix)
        COL = len(matrix[0])
        
        dp = [[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':
                    dp[r+1][c+1] = min(dp[r][c], dp[r+1][c], dp[r][c+1]) + 1
                    max_side = max(max_side, dp[r+1][c+1])
                
        return max_side * max_side

• 방법은 같지만 코드가 더 간결하다.
• 새로운 2차원 배열 dp를 선언하였고 시작부분에 열과 행을 하나씩 패딩한 사이즈로 만든다.
• 덮어쓰지 않고 matrix에서 1이 나오면 해당하는 위치의 dp에 채운다.