36. Valid Sudoku

难度: Medium

题目描述

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 '.'.

解题思路

代码实现

解决方案

java

class Solution {
    public boolean isValidSudoku(char[][] board) {

        Set<Character> set = null;
        // 行
        for (int i = 0; i < 9; i++) {
            set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c >= '0' && c <= '9') {
                    if (set.contains(c)) {

                        return false;
                    }
                    set.add(c);
                }

            }
        }
        // 列
        for (int i = 0; i < 9; i++) {
            set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char c = board[j][i];
                if (c >= '0' && c <= '9') {
                    if (set.contains(c)) {
                        return false;
                    }
                    set.add(c);
                }

            }
        }

        int[][] s = new int[][] {
                { 0, 0 },
                { 0, 1 },
                { 1, 0 },
                { -1, 0 },
                { 0, -1 },
                { 1, 1 },
                { -1, -1 },
                { -1, 1 },
                { 1, -1 } };

        for (int i = 1; i < 9; i += 3) {

            for (int j = 1; j < 9; j += 3) {
                set = new HashSet<>();
                for (int[] e : s) {
                    int x = i + e[0];
                    int y = j + e[1];
                    char c = board[x][y];
                    if (c >= '0' && c <= '9') {
                        if (set.contains(c)) {
                            return false;
                        }
                        set.add(c);
                    }
                }

            }

        }

        return true;

    }
}