# Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated **according to the following rules**:

1. Each row must contain the digits `1-9` without repetition.
2. Each column must contain the digits `1-9` without repetition.
3. Each of the 9 `3x3` sub-boxes of the grid must contain the digits `1-9` without repetition.

![img](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png) A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character `'.'`.

**Example 1:**

```
Input:
[
  ["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"]
]
Output: true
```

**Example 2:**

```
Input:
[
  ["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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
```

**Note:**

* A Sudoku board (partially filled) could be valid but is not necessarily solvable.
* Only the filled cells need to be validated according to the mentioned rules.
* The given board contain only digits `1-9` and the character `'.'`.
* The given board size is always `9x9`.

## 分析

* 如何建立正確的資料結構來進行紀錄
* 如何找出sub-boxes的規則
* Array(repeating:count) + Set混搭
* emurated()
* where條件
* Set的使用跟判斷

## 程式碼

```swift
class Solution {
    func isValidSudoku(_ board: [[Character]]) -> Bool {
        // 建立正確的資料結構來進行紀錄
        // - Array(repeating:count) + Set混搭
        var rowSets = Array(repeating: Set<Character>(), count: 9)
        var ColSets = Array(repeating: Set<Character>(), count: 9)
        var blockSets = Array(repeating: Set<Character>(), count: 9)

        // - emurated()
        // - where條件
        for (i, row) in board.enumerated() {
            for (j, char) in row.enumerated() where char != "." {
                // Set的使用
                if !rowSets[i].insert(char).inserted {
                    return false
                }
                if !ColSets[j].insert(char).inserted {
                    return false
                }
                // 找出sub-boxes的規則
                let block = (i / 3) + 3 * (j / 3)
                   if !blockSets[block].insert(char).inserted {
                    return false
                }
            }
        }

        return true

    }
```

## 複雜度

時間跟空間都是O(1), 因為題目已經說明 always `9x9`,所以總共就是81個格子要記錄，不會變多也不會變少，所以是常數時間跟空間。
