问题
Determine if a 9 x 9 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 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.
遍历并创建三组不同的哈希表,每个表内包含一组哈希集合。
如果访问的元素已在哈希集合内,则返回false
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| class Solution { public boolean isValidSudoku(char[][] board) { HashMap<Integer,HashSet<Character>> rowMap = new HashMap<Integer,HashSet<Character>>(); HashMap<Integer,HashSet<Character>> colMap = new HashMap<Integer,HashSet<Character>>(); HashMap<Integer,HashSet<Character>> blockMap = new HashMap<Integer,HashSet<Character>>();
for (int i = 0; i < board[0].length; i++ ){ for (int j = 0; j < board.length; j++ ){ char curChar = board[i][j]; if (curChar == '.'){ continue; } if (!rowMap.containsKey(i)){ rowMap.put(i, new HashSet<Character>()); } if (!colMap.containsKey(j)){ colMap.put(j, new HashSet<Character>()); } if (!blockMap.containsKey(j/3*3+i/3)){ blockMap.put(j/3*3+i/3, new HashSet<Character>()); } HashSet<Character> curRow = rowMap.get(i); HashSet<Character> curCol = colMap.get(j); HashSet<Character> curBlock = blockMap.get(j/3*3+i/3); if ( !curRow.contains(curChar) && !curCol.contains(curChar) && !curBlock.contains(curChar) ){ curRow.add(curChar); curCol.add(curChar); curBlock.add(curChar); } else{ return false; } } } return true; } }
|