publicstaticbooleanisValidSudoku(char[][] board){ Map<Integer, Set<Integer>> rowMap = new HashMap<>(); Map<Integer, Set<Integer>> colMap = new HashMap<>(); for (int i = 0; i < 9; i++) { rowMap.put(i, new HashSet<>()); colMap.put(i, new HashSet<>()); }
for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char ch = board[i][j]; if (ch != '.') { int num = ch - '0'; Set<Integer> rowSet = rowMap.get(i); if (!rowSet.add(num)) { returnfalse; }
publicstaticbooleanisValidSudoku_better(char[][] board){ Map<Integer, Set<Integer>> rowMap = new HashMap<>(); Map<Integer, Set<Integer>> colMap = new HashMap<>(); Map<Integer, Set<Integer>> subMap = new HashMap<>();
for (int i = 0; i < 9; i++) { rowMap.put(i, new HashSet<>()); colMap.put(i, new HashSet<>()); subMap.put(i, new HashSet<>()); }
for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char ch = board[i][j]; if (ch != '.') { int num = ch - '0'; Set<Integer> rowSet = rowMap.get(i); if (!rowSet.add(num)) { returnfalse; }
Set<Integer> colSet = colMap.get(j); if (!colSet.add(num)) { returnfalse; }
int subIdx = 3 * (i / 3) + j / 3; Set<Integer> subSet = subMap.get(subIdx); if (!subSet.add(num)) { returnfalse; } } } }
returntrue; }
Analysis
Time Complexity: O(1).
Space Complexity: O(1).
Array
Since numbers in Sudoku range from 1 to 9, we can use array instead of the HashMap for counting.
We create a 2D Array, the rows and columns which record the number of occurrences of each number in each row and column of Sudoku, and create a 3D Array subboxes to record the number of occurrences of each number in each sub-box.
If the count is greater than 1, the Sudoku is not valid.