36. Valid Sudoku (M)

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

Solution:

https://www.jiuzhang.com/problem/valid-sudoku/

解题思路

这题考查的是二维数组的遍历顺序。

判断每一行是否合法，外层循环枚举行，内层循环枚举列。

判断每一列是否合法，外层循环枚举列，内层循环枚举行。

判断每一块是否合法，每一块左上角的坐标都是(0, 0), (3, 0), (6, 0), (3, 0), (3, 3) ...，可以发现都是3的倍数，可以总结出规律，先枚举i = [0, 1, 2]，再枚举j = [0, 1, 2]，左上角坐标就是(i**3, j****3)。

代码思路

利用一个set来记录已经被用过的数，每次遍历一行，一列，一块，将访问过的元素加入set，冲突的话，返回false退出。最后返回true。

复杂度分析

假设这是一个N * N的数独，不止是9 * 9。

时间复杂度

• 要遍历3次这个数独，时间复杂度为O(N^2)。

空间复杂度

• 需要O(N)的空间，记录以用过的数。

源代码

javac++python

public class Solution {
    /**
     * @param board: the board
     * @return: whether the Sudoku is valid
     */
    public boolean isValidSudoku(char[][] board) {
        Set<Character> used = new HashSet();
        // 先枚举行，检查每行是否合法
        for (int row = 0; row < 9; row++) {
            used.clear();
            for (int col = 0; col < 9; col++) {
                if (! checkValid(board[row][col], used)) {
                    return false;
                }
            }
        }
        // 先枚举列，检查每列是否合法
        for (int col = 0; col < 9; col++) {
            used.clear();
            for (int row = 0; row < 9; row++) {
                if (! checkValid(board[row][col], used)) {
                    return false;
                }
            }
        }
        // 每个分块的左上角的坐标为(i * 3, j * 3)
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                used.clear();
                for (int row = i * 3; row < i * 3 + 3; row++) {
                    for (int col = j * 3; col < j * 3 + 3; col++) {
                        if (! checkValid(board[row][col], used)) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
    // 检查字符是否有冲突
    boolean checkValid(char c, Set<Character> used) {
        if (c == '.') {
            return true;
        }
        if (used.contains(c)) {
            return false;
        }
        used.add(c);
        return true;
    }
}