Share my Java solution with O(1) space && beats 95%


  • 0
    T

    Due to the matrix is 9 * 9, we only need to check at most 9 numbers each time. Considering that (1 << 9) do not exceed MAX_INT, so an Integer is enough to be used to mark whether a digit has appeared by implementation of bit operation.

    public class Solution {
        public boolean isValidSudoku(char[][] board) {
            int mask = 0, num = 0;
            for (int i = 0; i < 9; i ++) {
                mask = 0;
                for (int j = 0; j < 9; j ++) {
                    if (board[i][j] != '.') {
                        num = board[i][j] - '0';
                        if ((mask & (1 << num)) == 0) {
                            mask |= (1 << num);
                        } else {
                            return false;
                        }
                    }
                }
            }
            for (int j = 0; j < 9; j ++) {
                mask = 0;
                for (int i = 0; i < 9; i ++) {
                    if (board[i][j] != '.') {
                        num = board[i][j] - '0';
                        if ((mask & (1 << num)) == 0) {
                            mask |= (1 << num);
                        } else {
                            return false;
                        }
                    }
                }
            }
            for (int i = 0; i < 3; i ++) {
                for (int j = 0; j < 3; j ++) {
                    int x = i * 3;
                    int y = j * 3;
                    mask = 0;
                    for (int k = 0; k < 3; k ++) {
                        for (int l = 0; l < 3; l ++) {
                            if (board[x + k][y + l] != '.') {
                                num = board[x + k][y + l] - '0';
                                if ((mask & (1 << num)) == 0) {
                                    mask |= (1 << num);
                                } else {
                                    return false;
                                }
                            }
                        }
                    }
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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