NeetCodeのSolutionを書いていく

#

Valid Sudoku

#

問題概要

#

9x9の数独のボード board が与えられます。 数独のボードは以下のルールに従う場合に有効です。

1. それぞれの行が重複なく 1-9 の数字を含みます。
2. それぞれの列が重複なく 1-9 の数字を含みます。
3. 9つの 3x3 のサブボックスが重複なく 1-9 の数字を含みます。

例

#

Input: board = [[“1”,“2”,".",".",“3”,".",".",".","."], [“4”,".",".",“5”,".",".",".",".","."], [".",“9”,“8”,".",".",".",".",".",“3”], [“5”,".",".",".",“6”,".",".",".",“4”], [".",".",".",“8”,".",“3”,".",".",“5”], [“7”,".",".",".",“2”,".",".",".",“6”], [".",".",".",".",".",".",“2”,".","."], [".",".",".",“4”,“1”,“9”,".",".",“8”], [".",".",".",".",“8”,".",".",“7”,“9”]] Output: true

Input: board = [[“1”,“2”,".",".",“3”,".",".",".","."], [“4”,".",".",“5”,".",".",".",".","."], [".",“9”,“1”,".",".",".",".",".",“3”], [“5”,".",".",".",“6”,".",".",".",“4”], [".",".",".",“8”,".",“3”,".",".",“5”], [“7”,".",".",".",“2”,".",".",".",“6”], [".",".",".",".",".",".",“2”,".","."], [".",".",".",“4”,“1”,“9”,".",".",“8”], [".",".",".",".",“8”,".",".",“7”,“9”]] Output: false

制約

#

• boardsは9x9
• boardsの内容は 1-9 の数字か '.'

計算時間：O(n^2) メモリ：O(n^2)

メモ

#

列毎、行毎、サブボックス毎に値を確認すれば間違いない。 ただ、これをO(n^2)でやるにはどうしたらよいかという問。

計算時間がO(n^2)を許容しているので、単純に2重ループしながら、数の出現をチェックする。 行毎、列毎、サブボックス毎、に数の出現数をカウントしておく。 最後に全てのカウントが1以下である場合はTrueをそうでない場合はFalseを返せば良い。

結構自家なかかっちゃったけど、これなら計算時間はO(n^2)メモリもO(n^2)でOKだよね。

これって数独が解ける問題設定になっているかどうかは関係ないのかな？ 最初に条件をクリアしていれば必ず解ける(というかそれを探すのが数独)ということなのかな？

from typing import List


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        n = len(board)
        row_count = [[0] * 9 for _ in range(9)]
        col_count = [[0] * 9 for _ in range(9)]
        sbx_count = [[0] * 9 for _ in range(9)]

        for c in range(n):  # column(縦)方向への繰り返し
            for r in range(n):  # row(横)方向への繰り返し
                temp = board[c][r]
                if temp == ".":
                    continue
                val = int(temp) - 1

                row_count[r][val] += 1
                col_count[c][val] += 1
                sbx_count[((r // 3) + (c // 3) * 3)][val] += 1

        return (
            all([all([v <= 1 for v in val]) for val in row_count])
            and all([all([v <= 1 for v in val]) for val in col_count])
            and all([all([v <= 1 for v in val]) for val in sbx_count])
        )