A fast and straightforward python solution, 80ms


  • 0
    C

    ideas:

    use dictionary to store the elements. key: list of elements

    Scan all the elements that are not "." and return False as soon as we find an element that violates the rules.
    There are 3 types of keys: row number, column number, and sub-board.

    Since in each inner loop, we scan from the first to the last element in the SAME row, we can just use one key for row (re-initiate it at the beginning of the outer loop):

    1. d["Row"] ; 1 row
    2. d[j] ; j: column number ; n columns
    3. d[(i/3, j/3)] ; (i/3, j/3): sub-board number, (n/3)^2 sub-boards

    def isValidSudoku(self, board):
        d={j:[] for j in xrange(len(board[0]))} # column: list of elements
        for i in xrange(len(board)):
            d["Row"]=[]
            for j in xrange(len(board[0])):
                ele = board[i][j]
                if ele!=".":
                    if ele in d["Row"] or ele in d[j]:
                        return False
                    d["Row"].append(ele)
                    d[j].append(ele)   
                    if (i/3,j/3) in d: # sub-board (i/3,j/3)
                        if ele in d[(i/3,j/3)]:
                            return False
                        d[(i/3,j/3)].append(ele)
                    else:
                        d[(i/3,j/3)]=[ele]        
        return True
    

    Concise version: (same ideas, easier to read, but could be a little bit slower since we initiate all the empty lists in d at the beginning)

    def isValidSudoku(self, board):
        row=len(board)
        col=len(board[0])
        d={(i/3,j/3):[] for i in xrange(col) for j in xrange(row)}
        d.update({j:[] for j in xrange(col)})
        for i in xrange(row):
            d["Row"]=[]
            for j in xrange(col):
                ele=board[i][j]
                if ele!=".":
                    if ele in d["Row"] or ele in d[j] or ele in d[(i/3,j/3)]:
                        return False
                    d["Row"].append(ele)
                    d[j].append(ele) 
                    d[(i/3,j/3)].append(ele)                      
        return True

Log in to reply
 

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