My Simple O n^2 solution using bitset


  • 0
    H

    Using bitset of size 9 instead of a set.

    public class Solution {
        public boolean isValidSudoku(char[][] board) {
            if (null == board || board.length == 0) return false;
            BitSet bs = new BitSet(9);
            
            // check rows 
            for(int row=0; row<board.length; row++){
                bs.clear();
                for(int col=0; col<board[row].length; col++){
                    if(board[row][col] != '.'){
                          if(bs.get(board[row][col])){
                            return false;
                        }else{
                            bs.set(board[row][col]);
                        }
                    }
                }
            }
            
            // check cols
             for(int col=0; col<board[0].length; col++){
                bs.clear();
                for(int row=0; row<board.length; row++){
                    if(board[row][col] != '.'){
                        if(bs.get(board[row][col])){
                            return false;
                        }else{
                            bs.set(board[row][col]);
                        }
                    }
                }
            }
            
            // check 3 x 3 matrixes 
            for(int i=0 ; i <board.length; i++){
                for(int j=0; j<board[i].length; j++){
                    if(i%3 == 0 && j%3 == 0){
                        if(isValid(board, i, j) == false) return false;
                    }
                }
            }  
            return true;
        }
        
        boolean isValid(char[][] board, int startRow, int startCol){
            BitSet bs = new BitSet(9);
             for(int row=startRow; row<board.length && row < startRow+3; row++){
                for(int col=startCol; col<board[row].length && col < startCol+3; col++){
                    if(board[row][col] != '.' && bs.get(board[row][col])){
                        return false;
                    }else if(board[row][col] != '.'){
                        bs.set(board[row][col]);
                    }
                }
             }
            
            return true;
        }
    }
    

Log in to reply
 

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