C solution without any array or map or set


  • 0
    T

    I checked a lot of topics and almost every one uses Map or Set or something like that.
    Consider about that all numbers are less than 9, I used bit operation for repetition check.

    workflow:

    1. flag = 0
    2. we got a new number to check.
    3. flag = 1 << number & flag ? return false : 1 << number | flag

    Analysis:

    flag                             1 0 0 0 1 0 0 1 0
    number                         & 0 1 0 0 0 0 0 0 0
    --------------------------------------------------
    result                           0 0 0 0 0 0 0 0 0 
    

    In binary view, the position of each bit represents 1 to 9. When we got a number, we face two problems:

    1. How do we know number hasn't shown before?
      Set num = 1 << number, so we got a new num which has 1 in just its position and others with 0. Then we do flag & result, if the number hasn't shown before, the result must be 0000000002 = 010.
    2. How do we record the number?
      Since we already got num, just simply do flag |= num and I suppose you've already known how it works.

    C codes:

    bool isValidSudoku( char** board, int boardRowSize, int boardColSize ) {
        for (int i = 0; i < 9; i++) {
            int row = 0, column = 0, block = 0;
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = 1 << (board[i][j] - '0');
                    if (num & row) return false;
                    row |= num;
                }
    
                if (board[j][i] != '.') {
                    int num = 1 << (board[j][i] - '0');
                    if (num & column) return false;
                    column |= num;
                }
    
                int x = i / 3 * 3 + j / 3;
                int y = i % 3 * 3 + j % 3;
                if (board[x][y] != '.') {
                    int num = 1 << (board[x][y] - '0');
                    if (num & block) return false;
                    block |= num;
                }
            }
        }
        return true;
    }
    

  • 0
    W

    helpful,thanks


Log in to reply
 

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