[LeetCode]36. Valid Sudoku

36. Valid Sudoku

一、题目

Problem Description:
Determine if a 9 ∗ 9 9 * 9 9∗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 1-9 1−9 without repetition.
2. Each column must contain the digits 1 − 9 1-9 1−9 without repetition.
3. Each of the nine 3 ∗ 3 3 * 3 3∗3 sub-boxes of the grid must contain the digits 1 − 9 1-9 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 or ‘.’

二、题解

• 给出一个 9 ∗ 9 9*9 9∗9的数独棋盘，判断这个棋盘是否满足数独的要求：每行每列都只包含1-9，每个以粗实线划分的 3 ∗ 3 3*3 3∗3 九宫格内也只包含1-9。

• 注：此题不是求解数独，而是判断当前棋盘是否满足数独要求。

• 根据题目要求每行每列都只包含1-9，每个以粗实线划分的 3 ∗ 3 3*3 3∗3 九宫格内也只包含1-9可以进行以下划分：

  • 根据每行可划分为第0-8行；
  • 根据每列可划分为第0-8列；
  • 根据每个以粗实线划分的 3 ∗ 3 3*3 3∗3 九宫格可划分为第0-8块；
    
    块映射可通过公式： i / 3 ∗ 3 + j / 3 i/3*3+j/3 i/3∗3+j/3
    如：(5, 8)元素，经 i / 3 ∗ 3 + j / 3 i/3*3+j/3 i/3∗3+j/3计算，其位于 block #5

2.1 Approach #1 : Boolean Array

• 定义三个二维布尔型数组：rowArr[][]、colArr[][]、blockArr[][]

  • rowArr[][]包含了元素数值信息和行信息。第一维表示第 i 行，第二维表示第 i 行中是否存在数值为x的元素。
  • colArr[][]包含了元素数值信息和列信息。第一维表示第 i 列，第二维表示第 i 列中是否存在数值为x的元素。
  • blockArr[][]包含了元素值信息和块信息。第一维表示第 i 块，第二维表示第 i 行块中是否存在数值为x的元素。

• 注：这里采用的是Boolean Array，如果采用HashSet、HashMap等集合也同理。

Time complexity : O ( n 2 ) O(n^2) O(n2).
Space complexity : O ( n 2 ) O(n^2) O(n2).
n = b o a r d . l e n g t h n = board.length n=board.length

//Boolean Array
//Time complexity : O(n^2); Space complexity : O(n^2)
class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rowArr = new boolean[9][];
        boolean[][] colArr = new boolean[9][];
        boolean[][] blockArr = new boolean[9][];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                rowArr[i] = new boolean[9];
                colArr[i] = new boolean[9];
                blockArr[i] = new boolean[9];
            }
        }
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int numIndex = board[i][j] - '0' - 1;
                    if(rowArr[i][numIndex]
                    || colArr[j][numIndex]
                    || blockArr[i/3*3+j/3][numIndex])
                        return false;
                    else{
                        rowArr[i][numIndex] = true;
                        colArr[j][numIndex] = true;
                        blockArr[i/3*3+j/3][numIndex] = true;
                    }
                }
            }
        }
        return true;
    }
}

2.2 Approach #2 : Strings + HashSet

对于 9 ∗ 9 9*9 9∗9中的每个元素，其元素值分别附带行、列、块三个信息，根据一定的格式组成字符串，加入HashSet中。
如：(1, 4)值为9，则将“9 in row 1”、“9 in col 4”、“9 in block 1” 这三条字符串加入HashSet。
注：当然字符串格式可以根据人为定义，只要可以区分行、列、块信息即可。
如果 某一行 或 某一列 或 某一块 不满足数独要求，即存在重复数值，则组成的 行 或 列 或 块 的字符串信息就会重复。
通过set.add()返回的结果值即可判断是否存在重复的字符串。若重复，则返回false；整个棋盘遍历完成未出现重复，则最后返回true。

此方法通过“人为编码”，将行、列、块信息组成字符串，只需要用到一个HashSet即可，更简洁明了，易于理解。

Time complexity : O ( n 2 ) O(n^2) O(n2).
Space complexity : O ( n 2 ) O(n^2) O(n2).
n = b o a r d . l e n g t h n = board.length n=board.length

//Strings + HashSet
//Time complexity : O(n^2); Space complexity : O(n^2)
class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<String> set = new HashSet<String>();
        for(int i = 0; i < 9; i++){//i:row
            for(int j = 0; j < 9; j++){//j:column
                char c = board[i][j];
                if(c != '.'){
                    if((set.add(c + " in row " + i) == false)
                    || (set.add(c + " in col " + j) == false)
                    || (set.add(c + " in block " + i/3*3+j/3) == false)){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}