36. Valid Sudoku
1. Description
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
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.
2. Example
Example 1
Output: true
3. Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or ‘.’.
4. Solutions
Bitmask
Time complexity: O(1)
Space complexity: O(1)
class Solution {
public:
bool isValidSudoku(const vector<vector<char>> &board) {
array<int, 9> row_count{}, column_count{}, box_count{};
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char letter = board[i][j];
if (letter != '.') {
int digit = letter - '1';
int bit = 1 << digit;
int box = (i / 3) * 3 + (j / 3);
if ((row_count[i] & bit) > 0 || (column_count[j] & bit) > 0 ||
(box_count[box] & bit) > 0) {
return false;
}
row_count[i] |= bit;
column_count[j] |= bit;
box_count[box] |= bit;
}
}
}
return true;
}
};