36. Valid Sudoku 判断九九有效的数独

［抄题］：

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.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道怎么判断每个单独的3*3: 三倍行数遍历+一倍列数遍历进入具体的3*3

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

每一行都新建三个集合，然后行重复为[i][j] 列重复为[j][i]

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

三倍行数遍历+一倍列数遍历进入具体的3*3

［复杂度］：Time complexity: O(mn) Space complexity: O(mn)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        //for loop, judge row, col, and box
        for (int i = 0; i < 9; i++) {
            //initialization: 3 sets in each new row
            HashSet<Character> row = new HashSet<>();
            HashSet<Character> col = new HashSet<>();
            HashSet<Character> box = new HashSet<>();
            
            for (int j = 0; j < 9; j++) {
                //judge row, col
                if (board[i][j] != '.' && !row.add(board[i][j])) return false;
                if (board[j][i] != '.' && !col.add(board[j][i])) return false;
                //judge box
                //same for each row
                int rowIndex = 3 * (i / 3);
                System.out.println("rowIndex = " + rowIndex);
                int colIndex = 3 * (i % 3);
                System.out.println("colIndex = " + colIndex);
                System.out.println("-------------");
                //different for each col
                if (board[rowIndex + j / 3][colIndex + j % 3] != '.' && !box.add(board[rowIndex + j / 3][colIndex + j % 3])) return false;
            }
        }
    
        return true;
    }
}

View Code