關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers

LeetCode題目：36. Valid Sudoku
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 '.'.

Valid Sudoku

Note:

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

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int n = board.length;
        
        for(int i = 0; i < n; i++) {
            Set<Character> rows = new HashSet<Character>();
            Set<Character> columns = new HashSet<Character>();
            Set<Character> cubes = new HashSet<Character>();
            
            for(int j = 0; j < n; j++) {
                if(board[i][j] != '.') {
                    // check each row
                    if(rows.contains(board[i][j])) {
                        return false;
                    }
                    else {
                        rows.add(board[i][j]);
                    }
                }
                
                if(board[j][i] != '.') {
                    // check each column
                    if(columns.contains(board[j][i])) {
                        return false;
                    }
                    else {
                        columns.add(board[j][i]);
                    }
                }
                
                int rowIdx = 3 * (i / 3);
                int columnIdx = 3 * (i % 3);
                if(board[rowIdx + j / 3][columnIdx + j % 3] != '.') {
                    // check each cube
                    if(cubes.contains(board[rowIdx + j / 3][columnIdx + j % 3])) {
                        return false;
                    }
                    else {
                        cubes.add(board[rowIdx + j / 3][columnIdx + j % 3]);
                    }
                }
            }
        }
        
        return true;
    }
}

LeetCode題目：37. Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

Sudoku Solver

Sudoku Solver

class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        
        solve(board);
    }
    
    public boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == '.') {
                    // 嘗試每一個數(shù)字
                    for(char c = '1'; c <= '9'; c++) {
                        if(isValid(board, i, j, c)){
                            board[i][j] = c;
                            
                            // 遞歸，處理下一個位置
                            if(solve(board)) {
                                return true;
                            }
                            else {
                                // 回溯 backtracking
                                board[i][j] = '.';
                            }
                        }
                    }
                    
                    return false;
                }
            }
        }
        
        return true;
    }
    
    // 把(row, col)位置設(shè)為c，判斷是不是合法的數(shù)獨
    private boolean isValid(char[][] board, int row, int col, char c){
        for(int i = 0; i < 9; i++) {
            // 檢查第col列，不能有重復(fù)的c
            if(board[i][col] != '.' && board[i][col] == c) {
                return false;
            }
            
            // 檢查第row行，不能有重復(fù)的c
            if(board[row][i] != '.' && board[row][i] == c) {
                return false;
            }
            
            // 檢查對應(yīng)的cube，不能有重復(fù)的c
            if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' && 
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        
        return true;
    }
}