KK's blog

每天积累多一些

0%

LeetCode 036 Valid Sudoku

Posted on Disqus:

LeetCode



Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:



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:




Constraints:

board.length == 9 board[i].length == 9
board[i][j] is a digit or '.'. It is guaranteed that the input board has only one solution.

题目大意：

判断Sudoku是否合法

解题思路：

类似于Leetcode 037，用3个global的dict

解题步骤：

N/A

注意事项：

  1. 此题和L37有点不同，可以当版上的数是一个个填上的，所以无需初始化将数直接加入到dict中。而是每一位判断是否合法再加入。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def 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)

Free mock interview