36. Valid Sudoku

Question: Valid Sudoku

Solution

檢查 duplicate 就要想到可以用 hashset，簡單的概念可以先參考這一篇 [Contains Duplicate]

可以將 code 分成三個部份

1. 檢查每一個 row
   1. 用兩個 for 迴圈，先固定 y 軸，檢查 9 個 element 是否重複
2. 檢查每一個 column
   1. 用兩個 for 迴圈，先固定 x 軸，檢查 9 個 element 是否重複
3. 檢查每一個 3 * 3 的方格
   1. 將每個 element 的 x, y 都除以 3 取整數的部份，就可以將所有數字分成 9 大隔

   • ex:

     [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]

     x, y 都除以 3 取整數的部份會變成 [0, 0]

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # check rows
        square = defaultdict(set)
        for i in range(9): # fix position: y
            num_box = set()
            for j in range(9):
                ele = board[i][j] # fix y
                if ele == ".":
                    continue
                if ele in num_box:
                    return False
                else:
                    num_box.add(board[i][j])
        # check columns
        for i in range(9): # fix position: x
            num_box = set()
            for j in range(9):
                ele = board[j][i] # fix x
                if ele == ".":
                    continue
                if ele in num_box:
                    return False
                else:
                    num_box.add(board[j][i])
        # check 3 * 3
        for i in range(9):
            for j in range(9):
                ele = board[i][j] 
                if ele == ".":
                    continue
                k = i // 3        
                l = j // 3
                if ele in square[(k, l)]:
                    print(False)
                else:
                    square[(k, l)].add(ele)
        return True

Solution2

由上述方法改善
儲存 row, column, square 的 set
就可以只跑一次 9*9，用空間換時間，效果還不錯
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        column = defaultdict(set)
        row = defaultdict(set)
        square = defaultdict(set)
        for i in range(9):
            for j in range(9):
                ele = board[i][j]
                if ele == ".":
                    continue
                
                group = (i // 3, j // 3)
                if ele in row[i] or ele in column[j] or ele in square[group]:
                    return False
                row[i].add(ele)
                column[j].add(ele)
                square[group].add(ele)
        
        return True

Video Solution