# Leetcode 36. Valid sudoku

## 使用哈希表紀錄

### 使用列表記錄參數


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # (row // 3) * 3 + col // 3
        memo_col = [[] for i in range(9)]
        memo_row = [[] for i in range(9)]
        memo_sec = [[] for i in range(9)]
        rows = len(board)
        cols = len(board[0])

        def section(row: int, col: int): # 計算區塊公式
            return (row // 3) * 3 + col // 3
        
        for node in range(rows * cols):
            row = node // cols
            col = node % cols
            current_value = board[row][col]
            if current_value is ".":
                continue
            sec = section(row,col)

            if current_value in memo_col[col] or current_value in memo_row[row] or current_value in memo_sec[sec]:
                return False
            
            memo_row[row].append(current_value)
            memo_col[col].append(current_value)
            memo_sec[sec].append(current_value)

        return True

### 使用set紀錄參數


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # (row // 3) * 3 + col // 3
        memo_col = [set() for i in range(9)]
        memo_row = [set() for i in range(9)]
        memo_sec = [set() for i in range(9)]
        rows = len(board)
        cols = len(board[0])

        def section(row: int, col: int):
            return (row // 3) * 3 + col // 3
        
        for node in range(rows * cols):
            row = node // cols
            col = node % cols
            current_value = board[row][col]
            if current_value is ".":
                continue
            sec = section(row,col)

            if current_value in memo_col[col] or current_value in memo_row[row] or current_value in memo_sec[sec]:
                return False
            
            memo_row[row].add(current_value)
            memo_col[col].add(current_value)
            memo_sec[sec].add(current_value)

        return True

2023.7.21 AC

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        memo_x = [[] for i in range(9)]
        memo_y = [[] for i in range(9)]
        memo_s = [[[] for i in range(3)] for i in range(3)]

        for y in range(9):
            for x in range(9):
                val = board[y][x]
                if val is not ".":
                    if val in memo_x[x] or val in memo_y[y] or val in memo_s[y // 3][x // 3]:
                        return False
                    memo_x[x].append(val)
                    memo_y[y].append(val)
                    memo_s[y // 3][x // 3].append(val)
        
        return True

可以看出，set明顯更快，因為列表每次查詢時間為O(n)，而set每次只要O(1)