Valid Sudoku 389

Question

Determine whether a Sudoku is valid.

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

Notice

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Example

The following partially filed sudoku is valid.

Solution

分别检查行，列，小矩阵是否合法。用一个array来记录1-9是否被访问，每次检查新的之前要清空。（也可以用hashset来保存，不过array效率更高）。小矩阵每个cell的index也要注意。

代码如下：

class Solution {
    /**
      * @param board: the board
        @return: wether the Sudoku is valid
      */
    public boolean isValidSudoku(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0){
            return false;
        }

        boolean[] visited = new boolean[9];

        //row
        for(int i = 0; i < 9; i++){
            Arrays.fill(visited, false);
            for(int j = 0; j < 9; j++){
                if(!isValid(visited, board[i][j])){
                    return false;
                }
            }
        }

        //column
        for(int i = 0; i < 9; i++){
            Arrays.fill(visited, false);
            for(int j = 0; j < 9; j++){
                if(!isValid(visited, board[j][i])){
                    return false;
                }
            }
        }

        //submatrix
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                Arrays.fill(visited, false);
                for(int k = 0; k < 9; k++){
                    if(!isValid(visited, board[i + k / 3][j + k % 3])){
                        return false;
                    }
                }
            }
        }

        return true;
    }

    private boolean isValid(boolean[] visited, char c){
        //'.'
        if(c == '.'){
            return true;
        }

        int index = c - '0';
        if(index < 1 || index > 9 || visited[index - 1]){
            return false;
        }

        visited[index - 1] = true;
        return true;
    }
};