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.

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的使用跟判斷

程式碼

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個格子要記錄，不會變多也不會變少，所以是常數時間跟空間。