0036. Valid Sudoku

https://leetcode.com/problems/valid-sudoku

Description

Determine if a 9 x 9 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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

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.

Example 1:

**Input:** 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"]]
**Output:** true

Example 2:

**Input:** 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"]]
**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.

Constraints:

• board.length == 9

• board[i].length == 9

• board[i][j] is a digit 1-9 or '.'.

ac1: HashSet

set.add() will return boolean, to make your code consise

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 3 set: horizontal, vertical, matrix
        List<Set<Character>> hori = new ArrayList<Set<Character>>();
        List<Set<Character>> verti = new ArrayList<Set<Character>>();
        for (int i = 0; i < 9; i++) {
            hori.add(new HashSet<Character>());
            verti.add(new HashSet<Character>());
        }

        List<List<Set<Character>>> matr = new ArrayList<List<Set<Character>>>();
        for (int i = 0; i < 3; i++) {
            List<Set<Character>> tmp = new ArrayList<Set<Character>>();
            tmp.add(new HashSet<Character>());
            tmp.add(new HashSet<Character>());
            tmp.add(new HashSet<Character>());
            matr.add(tmp);
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;

                if (hori.get(r).contains(board[r][c])){
                    return false;
                } else {
                    hori.get(r).add(board[r][c]);
                }

                if (verti.get(c).contains(board[r][c])){
                    return false;
                } else {
                    verti.get(c).add(board[r][c]);
                }

                if (matr.get(r/3).get(c/3).contains(board[r][c])) return false;
                else matr.get(r/3).get(c/3).add(board[r][c]);
            }
        }

        return true;
    }
}

ac2: boolean[][]

faster and concise

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 3 boolean matrix
        // check current char is used or not
        boolean[][] hori = new boolean[9][10];
        boolean[][] verti = new boolean[9][10];
        boolean[][] cube = new boolean[9][10];

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;
                int val = board[r][c] - '0';
                int cubeIdx = (r/3) * 3 + c/3;

                if (hori[r][val] || verti[c][val] || cube[cubeIdx][val]) return false;
                hori[r][val] = true;
                verti[c][val] = true;
                cube[cubeIdx][val] = true;
            }
        }

        return true;
    }
}