Leetcode 36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/

Interesting problem. Direct way is to perform row scan and column scan and 3 x 3 scan. Or we can use Python's feature to make the code more concise.

Solution 1:

# T:O(n^2) S:O(n)
class Solution:
    # @param {character[][]} board
    # @return {boolean}
    def isValidSudoku(self, board):
        #row scan
        for i in xrange(9):
            syb = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
            for j in xrange(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] not in syb:
                    return False
                if board[i][j] in syb:
                    syb.remove(board[i][j])
        #col scan
        for i in xrange(9):
            syb = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
            for j in xrange(9):
                if board[j][i] == '.':
                    continue
                if board[j][i] not in syb:
                    return False
                if board[j][i] in syb:
                    syb.remove(board[j][i])
        #3x3scan
        c = [0, 3, 6]
        for h in c:
            for k in c:
                syb = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
                for i in xrange(h, h + 3):
                    for j in xrange(k, k + 3):
                        if board[i][j] == '.':
                            continue
                        elif board[i][j] not in syb:
                            return False
                        elif board[i][j] in syb:
                            syb.remove(board[i][j])
        return True

Run Time: 112 ms

Solution 2:

# T:O(n^2) S:O(n)
class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        for i in xrange(9):
            if not self.isValidList([board[i][j] for j in xrange(9)]) or not self.isValidList([board[j][i] for j in xrange(9)]):
                return False
        for i in xrange(3):
            for j in xrange(3):
                if not self.isValidList([board[m][n] for n in xrange(3 * j, 3 * j + 3) for m in xrange(3 * i, 3 * i + 3)]):
                    return False
        return True
    
    def isValidList(self, xs):
        xs = filter(lambda x: x != '.', xs)
        return len(set(xs)) == len(xs)

Run Time: 104 ms