---

题目

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 ‘.’ 表示。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 ‘.’

---

答案

有效的数独满足以下三个条件：

• 每一行中的数字都不重复；
• 每一列中的数字都不重复；
• 每一个 3×3 的宫格中的数字都不重复。

遍历数独，对于每个数字，判断其所在的行、列 以及 3×3 的宫格是否已经出现过该数字，如果是，则返回 false。遍历结束，返回 true。

时间复杂度 O©，空间复杂度 O©，其中 C 是数独中的空格数。本题中 C=81。

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        sub = [[False] * 9 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    continue
                num = int(c) - 1
                k = i // 3 * 3 + j // 3
                if row[i][num] or col[j][num] or sub[k][num]:
                    return False
                row[i][num] = True
                col[j][num] = True
                sub[k][num] = True
        return True

---

运行结果