M-36. Valid Sudoku

Loading...LeetCode

# 我的sb写法 ， O(1), O(1)
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def validate_rows():
            for i in range(9):
                appears = set() 
                for j in range(9):
                    num = board[i][j]
                    if num == ".":
                        continue
                    if num not in appears:
                        appears.add(num)
                    else:
                        return False
            return True
        
        def validate_columns():
            for j in range(9):
                appears = set() 
                for i in range(9):
                    num = board[i][j]
                    if num == ".":
                        continue
                    if num not in appears:
                        appears.add(num)
                    else:
                        return False
            return True

        def validate_squares():
            for i in range(0, 9, 3):
                for j in range(0, 9, 3):
                    row, col = i, j
                    appears = set()
                    for add_row in range(3):
                        for add_col in range(3):
                            num = board[i+add_row][j+add_col]
                            if num == ".":
                                continue
                            if num not in appears:
                                appears.add(num)
                            else:
                                return False
            return True
        return validate_rows() and validate_columns() and validate_squares()

# 看了答案之后的改进写法：
from collections import defaultdict
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        valid_rows = {v:defaultdict(int) for v in range(9)}
        valid_cols = {v:defaultdict(int) for v in range(9)}
        valid_squares = {(v,k):defaultdict(int) for v in range(3) for k in range(3)}
        for i in range(len(board)):
            for j in range(len(board[0])):
                number = board[i][j]
                if number == '.':
                    continue
                valid_rows[i][number] += 1
                valid_cols[j][number] += 1
                valid_squares[ (i//3,j//3)][number] += 1
                if valid_rows[i][number] > 1 or valid_cols[j][number] > 1 or valid_squares[(i//3,j//3)][number]>1:
                    return False
        return True

#原答案：
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]

        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == '.': 
                    continue
                num = int(num)
                box_index = (i // 3 ) * 3 + j // 3

                # keep the current cell value
                rows[i][num] = rows[i].get(num, 0) + 1
                columns[j][num] = columns[j].get(num, 0) + 1
                boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

                # check if this value has been already seen before
                if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                    return False         
        return True