# 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