36. Valid Sudoku (Easy)

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.

Solution 1: HashMap

对i行，列，block进行loop,找到第j个点对应board上的位置

using set: 29ms

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            set<char> row, col, cub;
            int rowIdx = 3*(i/3), colIdx = 3*(i%3);
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.' && row.count(board[i][j])) return false;
                row.insert(board[i][j]);
                if (board[j][i] != '.' && col.count(board[j][i])) return false;
                col.insert(board[j][i]);
                if (board[rowIdx+j/3][colIdx+j%3] != '.' && cub.count(board[rowIdx+j/3][colIdx+j%3])) return false;
                cub.insert(board[rowIdx+j/3][colIdx+j%3]);
            }
        }
        return true;
    }
};

using int array: 12ms

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            //vector<bool> row(9, false), col(9,false), cub(9,false);
            bool row[9] = {false}, col[9] = {false}, cub[9] = {false};
            int rowIdx = 3*(i/3), colIdx = 3*(i%3);
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    if (row[board[i][j]-'1']) return false;
                    row[board[i][j]-'1'] = true;
                }
                if (board[j][i] != '.') {
                    if (col[board[j][i]-'1']) return false;
                    col[board[j][i]-'1'] = true;
                }

                if (board[rowIdx+j/3][colIdx+j%3] != '.') {
                    if (cub[board[rowIdx+j/3][colIdx+j%3]-'1']) return false;
                    cub[board[rowIdx+j/3][colIdx+j%3]-'1'] = true;
                }

            }
        }
        return true;
    }
};

Solution 2: Bit Manipulation 9ms!

对board上每个点loop,找到它所在的行，列与block的编号（0-8）。 用short的bit来对应每一位数字。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        short row[9] = {0}, col[9] = {0}, cub[9] = {0};
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    short idx = 1 << (board[i][j] - '0');
                    if (row[i] & idx || col[j] & idx || cub[(i/3)*3+j/3] & idx) return false;
                    row[i] |= idx;
                    col[j] |= idx;
                    cub[(i/3)*3+j/3] |= idx;
                }
            }
        }
        return true;

    }
};