LeetCode: Maximal Squareを解く

問題

LeetCode 30-Day LeetCoding Challenge 27日目です。 あと3問で終わりです。

leetcode.com

パット見 Max Area of Islandとかの類問かと思いきや 見つけ出すのがSquare=正方形というのがポイントです。

解き方

www.youtube.com

DFSを使って解く、と思いきやDPを使って解きます。 （DFS使っても解ける気がするんだけど）

正方形ってのが漸化式を作りやすいので、なるほどなという感想。 以下の漸化式を立てればOK

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

これは正方形の見た目のまんまですね。 ただし、1番目の行、列には上記の漸化式は適用せずそのまま、値をコピーする。 (i-1, j-1が無いため)

回答

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, cols = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
        dp = [[0 for _ in range(cols)] for _ in range(rows)]
        maxLength = 0
        for i in range(rows):
            for j in range(cols):
                if i == 0 or j == 0:
                    dp[i][j] = int(matrix[i][j])
                    maxLength = max(dp[i][j], maxLength)
                elif matrix[i][j] == "1":
                    dp[i][j] = min(int(dp[i][j-1]), int(dp[i-1][j]), int(dp[i-1][j-1])) + 1
                    maxLength = max(dp[i][j], maxLength)
                
                
        return maxLength ** 2
                
        

ちなみにdpを行列+1の大きさでつくることで、for文中の1行目判定を無くすことができる。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, cols = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
        dp = [[0 for _ in range(cols+1)] for _ in range(rows+1)]
        maxLength = 0
        for i in range(1, rows+1):
            for j in range(1, cols+1):
                if matrix[i-1][j-1] == "1":
                    dp[i][j] = min(int(dp[i][j-1]), int(dp[i-1][j]), int(dp[i-1][j-1])) + 1
                    maxLength = max(dp[i][j], maxLength)
                
                
        return maxLength ** 2