Alex Blog

36. Valid Sudoku

2019/11/06 Leetcode

36. Valid Sudoku

Tags: ‘Hash Table’

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.

Solution

$O(n) O(n)$

可以用array 代替hashmap， 如果key数值是固定范围

public boolean isValidSudoku(char[][] board) {
    // memorization using hashmap<index, count> for 
    // row 1-9 column1-9 box1-9
    int[][] rows = new int[9][9];
    int[][] columns = new int[9][9];
    int[][] boxes = new int[9][9];
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int n = Character.getNumericValue(board[i][j]) - 1; 
                int box_index = i/3 * 3 + j/3;
                rows[i][n] = rows[i][n] + 1;
                columns[j][n] = columns[j][n] + 1;
                boxes[box_index][n] = boxes[box_index][n] + 1;
                
                if (rows[i][n] > 1 || columns[j][n] > 1 || boxes[box_index][n] > 1) {
                    return false;
                }
            }
            
        }
    }
    return true;
}

Search

    Table of Contents