AC concise Python code

  • 5

    The brute force algorithm is creating the hash-tables to detect the existed number.
    for each item, we need to check the col, row and the squares(3*3).
    so we need totally 9 hashtables for the col, 9 hashtables for the row and 9 hashtables for the squares
    we can optimize both the hashtables and hash function by the fact that value of each item is
    {0,1,2 ... ,9}. (i.e. we could use nth bit denote whether n exist)

       class Solution:
            # @param board, a 9x9 2D array
            # @return a boolean
            def isValidSudoku(self, board):
                if board == None:
                    return False
                _row= [0 for i in range(9)]
                _col= [0 for i in range(9)]
                _blo= [0 for i in range(9)]
                for i in range(len(board)):
                    for j in range(len(board[0])):
                        if board[i][j] != ".":
                            _tem = 1<< (int)(board[i][j])
                            _ind = (i/3) * 3 + j/3
                            if _tem & _row[j] or _tem & _col[i] or _tem & _blo[_ind]:
                                return False
                                _col[i] = _col[i] | _tem
                                _row[j] = _row[j] | _tem
                                _blo[_ind] = _blo[_ind] | _tem
                return True

Log in to reply

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