Skip to content

Latest commit

 

History

History
99 lines (88 loc) · 3.02 KB

36. Valid Sudoku.md

File metadata and controls

99 lines (88 loc) · 3.02 KB
Raw

36. Valid Sudoku

Difficulty : Medium

Related Topics : HashTable

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.
  • Each column must contain the digits 1-9 without repetition.
  • Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

1

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

  • mine
    • Java
      • Runtime: 2 ms, faster than 87.53%, Memory Usage: 42.9 MB, less than 26.65% of Java online submissions 
        // O(R*C)time
// O(R)space
public boolean isValidSudoku(char[][] board) {
    int[] r = new int[10];
    int[] c = new int[10];
    int[] nine = new int[10];
    for(int i = 0; i < board.length; i++){
        for(int j = 0; j < board[i].length; j++){
            if(board[i][j] == '.')continue;
            int v = board[i][j] - '0';
            int t = 1 << v;
            int index = i / 3 * 3 + j / 3;
            if((r[i] & t) != 0 || (c[j] & t) != 0 || (nine[index] & t) != 0){
                return false;
            }
            r[i] += t;
            c[j] += t;
            nine[index] += t;
        }
    }

    return true;
}