36-valid-sudoku

36. Valid Sudoku (Medium) (https://leetcode.com/problems/valid-sudoku/)

Определите, является ли доска 9 x 9 для судоку допустимой. Проверять нужно только заполненные ячейки согласно следующим правилам: 1. Каждая строка должна содержать цифры 1-9 без повторений. 2. Каждый столбец должен содержать цифры 1-9 без повторений. 3. Каждый из девяти квадратов 3 x 3 сетки должен содержать цифры 1-9 без повторений. Примечание: - Доска судоку (частично заполненная) может быть допустимой, но не обязательно разрешимой.

• Проверять по указанным правилам нужно только заполненные ячейки. Ограничения: - board.length 9 - board[i].length 9 - board[i][j] это цифра 1-9 или ’.’.

function isValidSudoku(board: string[][]): boolean {
  const rowSet = new Set<string>()
  const colSets: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>())
  const squareSets: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>())
 
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === ".") continue
      // column
      if (colSets[j].has(board[i][j])) return false
      colSets[j].add(board[i][j])
      // row
      if (rowSet.has(board[i][j])) return false
      rowSet.add(board[i][j])
      // square
      const squareIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)
      if (squareSets[squareIndex].has(board[i][j])) return false
      squareSets[squareIndex].add(board[i][j])
    }
    rowSet.clear()
  }
  return true
}
 
// Локальная проверка:
console.log(
  isValidSudoku([
    ["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"],
  ]),
) // true
 
console.log(
  isValidSudoku([
    ["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"],
  ]),
) // false

Пример 1:
 
    Ввод: board = [["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"]]
    Вывод: true
 
Пример 2:
 
    Ввод: board = [["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"]]
    Вывод: false
    Объяснение: То же, что и в примере 1, за исключением того, что 5 в левом верхнем углу изменена на 8. Поскольку в левом верхнем квадрате 3x3 есть две восьмёрки, доска недопустима.

leetcode