Leetcode-36 Valid Sudoku

发表于 | 分类于 | 次

Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Example 1

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
[
  ["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: true

Example 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input:
[
  ["8","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: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

解题思路

遍历每个单元，判断是否合法，碰到 '.' 则跳过。碰到数字需要检测横竖方向和九宫格内是否存在冲突数字。

复杂度分析

  • 时间复杂度：$O(n^3)$，每次检测需要 $O(n)$ 复杂度。
  • 空间复杂度：$O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
	bool isValidSudoku(vector<vector<char>>& board) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				if (board[i][j] == '.') continue;
				char num = board[i][j];
				board[i][j] = '.';
				if (!isValid(board, i, j, num)) return false;
				board[i][j] = num;
			}
		}
		return true;
	}

	bool isValid(vector<vector<char>>& board, int pi, int pj, char num) {
		for (int i = 0; i < 9; ++i) {
			if (board[i][pj] == num) return false;
			if (board[pi][i] == num) return false;
			if (board[pi / 3 * 3 + i / 3][pj / 3 * 3 + i % 3] == num) return false;
		}
		return true;
	}
};