36. Valid Sudoku.md

36. Valid Sudoku

Question:

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Example 1:

Input:
[
  ["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:
[
  ["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.

Thinking:

• Method:

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < 9; i++){
            Set<Character> set1 = new HashSet<>();
            Set<Character> set2 = new HashSet<>();
            for(int j = 0; j < 9; j++){
                char c1 = board[i][j];
                char c2 = board[j][i];
                if(set1.contains(c1) && c1 != '.')
                    return false;
                set1.add(c1);
                if(set2.contains(c2) && c2 != '.')
                    return false;
                set2.add(c2);
            }
        }
        for(int i = 0; i < 9; i+=3){
            for(int j = 0; j < 9; j+=3){
                Set<Character> set = new HashSet<>();
                for(int p = i; p < i + 3; p++){
                    for(int q = j; q < j + 3; q++){
                        char c = board[p][q];
                        if(set.contains(c) && c != '.')
                            return false;
                        set.add(c);
                    }
                }
            }
        }
        return true;
    }
}

二刷

1. 使用集合

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character> set1 =  null;
        Set<Character> set2 =  null;
        for(int i = 0; i < 9; i++){
            set1 = new HashSet<Character>();
            set2 = new HashSet<Character>();
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    if(set1.contains(board[i][j])) return false;
                    set1.add(board[i][j]);
                }
                if(board[j][i] != '.'){
                    if(set2.contains(board[j][i])) return false;
                    set2.add(board[j][i]);
                }
            }
        }
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                set1 = new HashSet<Character>();
                for(int p = i % 3; p < 3; p++){
                    for(int q  = j % 3; q < 3; q++){
                        if(board[i + p][j + q] != '.')
                            if(set1.contains(board[i + p][j + q])) return false;
                        set1.add(board[i + p][j + q]);
                    }
                }
            }
        }
        return true;
    }
}

2. 使用数组充当集合

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] set1 =  null;
        int[] set2 =  null;
        for(int i = 0; i < 9; i++){
            set1 = new int[9];
            set2 = new int[9];
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    if(set1[board[i][j] - '1'] != 0) return false;
                    set1[board[i][j] - '1']++;
                }
                if(board[j][i] != '.'){
                    if(set2[board[j][i] - '1'] != 0) return false;
                    set2[board[j][i] - '1']++;
                }
            }
        }
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                set1 = new int[9];
                for(int p = i % 3; p < 3; p++){
                    for(int q  = j % 3; q < 3; q++){
                        if(board[i + p][j + q] != '.'){
                            if(set1[board[i + p][j + q] - '1'] != 0) return false;
                            set1[board[i + p][j + q] - '1']++;
                        }
                    }
                }
            }
        }
        return true;
    }
}