<div>
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
<pre>Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] Explanation: The input board is shown above and the only valid solution is shown below:
</pre>
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
</div>
题目大意：
判断Sudoku是否合法
解题思路：
类似于Leetcode 037，用3个global的dict
解题步骤：
N/A
注意事项：
- 此题和L37有点不同，可以当版上的数是一个个填上的，所以无需初始化将数直接加入到dict中。而是每一位判断是否合法再加入。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def isValidSudoku(self, board: List[List[str]]) -> bool:
row_dict = [collections.defaultdict(int) for _ in range(len(board))]
col_dict = [collections.defaultdict(int) for _ in range(len(board))]
box_dict = [collections.defaultdict(int) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == '.':
continue
if not self.is_valid(i, j, board[i][j], row_dict, col_dict, box_dict):
return False
row_dict[i][board[i][j]] = 1
col_dict[j][board[i][j]] = 1
box_dict[i // 3 * 3 + j // 3][board[i][j]] = 1
return True
def is_valid(self, i, j, val, row_dict, col_dict, box_dict):
if val in row_dict[i] or val in col_dict[j] or val in box_dict[i // 3 * 3 + j // 3]:
return False
return True
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
