问题
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
例子
A partially filled sudoku which is valid.
分析
数独的大小为9x9，可以分成9块，每一块大小为3x3。典型的数独如下图所示：
经典数独
数独的规则：
- 每个横向和纵向行的数字不能重复，必须有且仅有1-9这9个数字；
- 每块的数字不能重复，必须有且仅有1-9这9个数字。
题目要求验证数独的正确性，我们只需要对已有的数字验证上面两条规则就可以了。
要点
- 理解数独的规则；
- 使用unordered_set判断数字是否已经存在。
时间复杂度
O(n^2)，n为数独的大小（长或宽），n一般来说是9
空间复杂度
O(n)
代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
unordered_set<char> rs, cs;
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.' && rs.find(board[i][j]) != rs.end()) return false;
else rs.insert(board[i][j]);
if (board[j][i] != '.' && cs.find(board[j][i]) != cs.end()) return false;
else cs.insert(board[j][i]);
}
}
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
unordered_set<char> bs;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (board[i + x][j + y] != '.' && bs.find(board[i + x][j + y]) != bs.end()) return false;
else bs.insert(board[i + x][j + y]);
}
}
}
}
return true;
}
};
