LeetCode 5日目振り返りやっていきます。
36. Valid Sudoku
問題文
9×9の数独の盤面が有効かどうかを判定する。以下のルールに従って、塗りつぶされたセルだけを検証する必要がある:
各行には、1~9の数字が繰り返しなく含まれていること。 各列には1〜9の数字が重複なく含まれていなければならない。 3×3の9つのサブボックスは、それぞれ1~9の数字が重複なく含まれていなければならない。
注意してください:
数独の盤面が部分的に埋まっているものは、有効である可能性があるが、必ずしも解けるとは限らない。 埋められたセルだけが、前述のルールに従って検証される必要があります。
制約条件
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'.
解答
function isValidSudoku(board: string[][]): boolean { const col = Array.from({ length: 9 }, () => new Set()); const row = Array.from({ length: 9 }, () => new Set()); const box = Array.from({ length: 3 }, () => Array.from({ length: 3 }, () => new Set()) ); for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { const cell = board[i][j]; if (cell === '.') { continue; } const x = Math.floor(i / 3); const y = Math.floor(j / 3); if (col[i].has(cell) || row[j].has(cell) || box[x][y].has(cell)) { return false; } col[i].add(cell); row[j].add(cell); box[x][y].add(cell); } } return true; };
振り返り
ハッシュテーブルを使って3つの条件それぞれ9つの入れものを作って値をチェックする方法で実装しました。
3x3のサブボックスの配列の持ち方をどうするのか悩んだんですが。
自分は2次元配列の中にハッシュテーブルを格納する形で解きました。
ほかの人の解答を見ると別の方法で解いていたりするので面白いですね。
最初はハッシュテーブルの使い方があまり理解できていなかったですが。 直近は使い方がわかるようになってきていい感じです!