(Medium) LeetCode - Valid Sudoku

tags: Go

category: LeetCode

description: LeetCode - Valid Sudoku

created_at: 2021/08/08 22:00:00

題目連結: https://leetcode.com/problems/valid-sudoku/

前言

在很久以前在 LeetCode 上看到這題的時候，本來以為是要判斷很多(包含有無解)，結果在今天仔細看題目的時候發現原來只要判斷是否符合規則，而不用判斷是否有解，這樣難度就大幅降低了。

簡介

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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

上面這是數獨的規則也是題目的規則，只要每一欄、列、方格中的1~9不重複就可以，邏輯很單純，核心的話應該就是第三點的計算。

下面一樣附上 Go 的程式碼，通過之後去看 0ms 的解，發現超暴力的XD，真的就是為了求快不擇手段。

import "fmt"

// 判斷 key 是否存在 map 中
func Contains(m map[byte]struct{}, key byte) bool {
    _, ok := m[key]
    return ok
}

// 求出題目第三條規則，給ij算屬於哪個框
func GetMapIndex(i int, j int) int {
    i /= 3
    j /= 3
    return i * 3 + j
}

func isValidSudoku(board [][]byte) bool {
    /*
        先建立一個3*9的map並初始化
        01分別代表9欄/列
        2 代表9個小方格
    */
    var m = [3][9]map[byte]struct{}{}
    for i := range m {
        for j := range m[i] {
            m[i][j] = make(map[byte]struct{})
        }
    }

    // 走訪每個格子
    for i := range board {
        for j := range board[i] {
            // 不是空格才做判斷
            if board[i][j] != '.' {
                // 建立陣列少打一點字，存欄列與小方格的索引
                indexes := []int {i, j, GetMapIndex(i, j)}
                for k := range indexes {
                    // 如果重複了就 false
                    if Contains(m[k][indexes[k]], board[i][j]) {
                        return false
                    }
                    // 不然就丟進map紀錄
                    m[k][indexes[k]][board[i][j]] = struct{}{}
                }
            }
        }
    }

    // 都沒重複當然後true啦
    return true
}