Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 36. Valid Sudoku

tags: leetcode

問題

イデア

縦,横,斜めそれぞれに1-9が重複していないかを確かめます.

おそらくやるだけです…

解法

書きます.

計算量

ボードの1辺の長さを$N$とします.($N=9$ですが)

  • 時間計算量
    • is_validメソッドは$O(N)$必要です.
    • これをそれぞれ$N$行,列,対角線で使っているので$O(N2)$
  • 空間計算量
    • $O(N)$

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        return (self.is_row_valid(board) and
                self.is_col_valid(board) and
                self.is_square_valid(board))
        
    def is_valid(self, unit: List[str]) -> bool:
        unit = [i for i in unit if i != '.']
        return len(set(unit)) == len(unit)

    def is_row_valid(self, board: List[List[str]]) -> bool:
        for row in board:
            if not self.is_valid(row):
                return False
        return True
    
    def is_col_valid(self, board: List[List[str]]) -> bool:
        for col in zip(*board):
            if not self.is_valid(col):
                return False
        return True
    
    def is_square_valid(self, board: List[List[str]]) -> bool:
        for i in (0, 3, 6):
            for j in (0, 3, 6):
                square = [board[x][y] for x in range(i, i+3) for y in range(j, j+3)]
                if not self.is_valid(square):
                    return False
        return True