一、题目
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
image
<small style="box-sizing: border-box; font-size: 10.399999618530273px;">上图是一个部分填充的有效的数独。</small>
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字
1-9和字符'.'。 - 给定数独永远是
9x9形式的。
二、解题
直接遍历二维数组，在第二个for循环里判断每个元素，在其对应的行、列已经子数独里验证是否有重复数字即可。
先创建三个字典rowDict:[Int:[Character:Int]]（存储所有行的数字），columnDict: [Int:[Character:Int]]（存储所有列的数字），boxDict: [Int:[Character:Int]]（存储所有3x3子数独中的数字）。
这里有个难点，就是子数独的位置计算let bIndex = i / 3 * 3 + j / 3。
详细请看代码：
时间复杂度：O(m*n)。(假设board[m][n])
三、代码实现
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
var rowDict: [Int:[Character:Int]] = [:]
var columnDict: [Int:[Character:Int]] = [:]
var boxDict: [Int:[Character:Int]] = [:]
for i in (0..<9) {
for j in (0..<9) {
let c = board[i][j]
if c == "." {
continue
}
if rowDict[i] == nil {
rowDict[i] = [:]
}
if rowDict[i]![c] != nil {
return false
}else{
rowDict[i]![c] = 1
}
if columnDict[j] == nil {
columnDict[j] = [:]
}
if columnDict[j]![c] != nil {
return false
}else{
columnDict[j]![c] = 1
}
let bIndex = i / 3 * 3 + j / 3
if boxDict[bIndex] == nil {
boxDict[bIndex] = [:]
}
if boxDict[bIndex]![c] != nil {
return false
}else {
boxDict[bIndex]![c] = 1
}
}
}
return true
}
}
Demo地址：github
