Valid Sudoku

一直以为这是个很复杂的题，其实就是哈希表找行列对角线重复就行了

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        n = len(board)
        m = len(board[0])
        for i in xrange(9):
            rowCheck = set()
            colCheck = set()
            for j in xrange(9):
                if board[i][j] != '.' and board[i][j] in rowCheck:
                    return False
                if board[j][i] != '.' and board[j][i] in colCheck:
                    return False
                rowCheck.add(board[i][j])
                colCheck.add(board[j][i])

        for i in xrange(0, 9, 3):
            for j in xrange(0, 9, 3):
                check = set()
                for row in xrange(i, i + 3):
                    for col in xrange(j, j + 3):
                        if board[row][col] != '.' and board[row][col] in check:
                            return False
                        check.add(board[row][col])

        return True

这道题和N皇后一样，对于特殊的查重位有很巧妙的检查方式，N皇后中是对角线的横纵坐标和差为定值，而这里我们可以根据单行里面的1到9这9个数是否有出现来检查，行列不用说了，这里对每个subbox是利用的和正常矩阵一样的方式来检查，其实就可以把subbox看成3*3的矩阵就行了，所以这里对i和j做一个特殊处理就行，很容易理解的方法

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        n = len(board)
        if not n:
            return False

        m = len(board[0])
        if not m:
            return False

        row = [[0] * 9 for _ in xrange(9)]
        col = [[0] * 9 for _ in xrange(9)]
        sub = [[0] * 9 for _ in xrange(9)]

        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] != '.':
                    num = ord(board[i][j]) - ord('0') - 1
                    region = i / 3 * 3 + j / 3
                    if row[i][num] or col[j][num] or sub[region][num]:
                        return False
                    row[i][num], col[j][num], sub[region][num] = 1, 1, 1

        return True