Description
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 ‘.’.
A partially filled sudoku which is valid.
Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Discussion
判断一个给定的9*9矩阵是否满足数独的规则，只考虑已经填充的数字。
我们需要把每行进行一次判断，每列进行一次判断，每个九宫格进行一次判断。
第i行的第j个元素的坐标为board[i][j] 第i列的第j个元素的坐标为board[j][i] 第i个九宫格中第j个元素的坐标为board[i/33 + j/3][i%33 + j%3]
算法的时间复杂度为O(n^2)。
C++ Code
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//下面遍历第i行／列／个九宫格中的第j个数。
for(int i = 0; i < 9; i++)
{
unordered_map<char, int> row_map; //检查第i行
unordered_map<char, int> col_map; //检查第i列
unordered_map<char, int> subgrid_map; //检查第i个九宫格
for(int j = 0; j < 9; j++)
{
//第i行的第j个元素的坐标为board[i][j]
if(board[i][j] != '.')
{
row_map[board[i][j]] ++;
if(row_map[board[i][j]] > 1)
{
return false;
}
}
//第i列的第j个元素的坐标为board[j][i]
if(board[j][i] != '.')
{
col_map[board[j][i]] ++;
if(col_map[board[j][i]] > 1)
{
return false;
}
}
//第i个九宫格中第j个元素的坐标为board[i/3*3 + j/3][i%3*3 + j%3]
if(board[i/3*3 + j/3][i%3*3 + j%3] != '.')
{
subgrid_map[board[i/3*3 + j/3][i%3*3 + j%3]] ++;
if(subgrid_map[board[i/3*3 + j/3][i%3*3 + j%3]] > 1)
{
return false;
}
}
}
}
return true;
}
};