面试150 有效的数独

思路

我们需要通过建立三个哈希集合去记录每一行，每一列、以及该位置所属3x3小宫格内已出现的数字。遍历整个棋盘，如果当前不是空格，检查数字是否出现在第i行的rows[i]中或者第j列的cols[j]或者是3x3小格box[i//3][j//3],如果出现了，则说明不合法，直接返回False。如果是合法，将数字c讲到对应的集合中，方便后续判断。

class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:if not board:return Falsem=len(board)n=len(board[0])rows=[set() for _ in range(9)]cols=[set() for _ in range(9)]box=[[set() for _ in range(3)] for _ in range(3)]for i in range(m):for j in range(n):c=board[i][j]if board[i][j]!='.':if c in rows[i] or c in cols[j] or c in box[i//3][j//3]:return Falserows[i].add(c)cols[j].add(c)box[i//3][j//3].add(c)return True