My C++ code (O(n2) time and space)


  • 5
    D

    The basic idea is to use an array to indicate whether a number in a row/column/3x3 sub-block already occurs. We need a 9x9 array existNum and
    a) the LSB of existNum[i][j] indicates whether number j occurs on the i-th row before
    b) the 2-LSB of existNum[i][j] indicates whether number j occurs on the i-th column before
    c) the 3-LSB of existNum[i][j] indicates whether number j occurs on the i-th sub-block before, k= (i/3)*3 + j/3

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char> > &board) {
            char existNum[10][10]={0};
            int i,j;
            
            for(i=0; i<9; i++)
            {
                for(j=0; j<9; j++)
                {
                    if(board[i][j]!='.')
                    {
                        if(existNum[i][board[i][j] - '0'] & 0x1)return false; // check if the i-row already has such number, LSB
                        if(existNum[j][board[i][j] - '0'] & 0x2) return false; // check if the j-col already has such number, 2-LSB
                        if(existNum[(i/3) *3 + j/3][board[i][j] - '0'] & 0x4) return false; // check if the k-subblock already has such number, 3-LSB
                        existNum[i][board[i][j] - '0'] ^=0x1;
                        existNum[j][board[i][j] - '0'] ^=0x2;
                        existNum[(i/3) *3 + j/3][board[i][j] - '0'] ^=0x4;
                    }
                    
                }
            }
            
            return true;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.