Valid Sudoku

• leetcode 36
• Easy
• Company Tags: Snapchat, Uber, Apple
• Similar Problems: Sudoku Solver;

Description

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Previous Thinking

check the conditions for each position. The hints given recommend using HashSet. However, I think using array is more easy understanding.

C++ Solution

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool check_column[9][9] = {false};
        bool check_row[9][9] = {false};
        bool check_block[9][9] = {false};

        for(int i = 0; i < 9; ++i ){
            for(int j = 0; j < 9; ++j){
                if(board[i][j] != '.'){
                    int temp = board[i][j] - '1';
                    if(check_row[i][temp] || check_column[j][temp] || check_block[i / 3 * 3 + j / 3][temp]){
                          return false;
                    }else{
                        check_column[j][temp] = true;
                        check_row[i][temp] = true;
                        check_block[i / 3 * 3 + j / 3 ][temp] = true;
                    }
                }
            }
        }

        return true;
    }
};

Java Solution

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] check_row = new boolean[9][9];
        boolean[][] check_column = new boolean[9][9];
        boolean[][] check_block = new boolean[9][9];

        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                if(board[i][j] != '.'){
                    int temp = board[i][j] - '1';
                    if(check_row[i][temp] || check_column[j][temp] || check_block[i / 3 * 3 + j / 3][temp]){
                        return false;
                    }else{
                        check_row[i][temp] = true;
                        check_column[j][temp] = true;
                        check_block[i / 3 * 3 + j / 3][temp] = true;
                    }

                }
            }
        }
        return true;
    }
}

Notice

• initialization rules of Array are different in C++ and Java
• Encoding method is the tricky part.