Straight forward java solution beat 95%


  • 0
    C

    I Used three boolean double arrays to replace the isValid function. It can save some running time.

    public class Solution {
        public void solveSudoku(char[][] board) {
            boolean[][] rows = new boolean[9][9];
            boolean[][] cols = new boolean[9][9];
            boolean[][] box = new boolean[9][9];
            
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (board[i][j] != '.') {
                        int num = board[i][j] - '1';
                        int k = i / 3 * 3 + j / 3;
                        rows[i][num] = true;
                        cols[j][num] = true;
                        box[k][num] = true;
                    }
                }
            }
            helper(board, rows, cols, box, 0);
        }
        
        private boolean helper(char[][] board, boolean[][] rows, boolean[][] cols, boolean[][] box, int index) {
            if (index >= 81)
                return true;
            int x = index / 9;
            int y = index % 9;
            if (board[x][y] != '.') {
                return helper(board, rows, cols, box, index + 1);
            } else {
                char c = '1';
                for (; c <= '9'; c++) {
                    if ((!rows[x][c - '1']) && (!cols[y][c - '1']) && (!box[(x/3)*3+y/3][c-'1'])) {
                        rows[x][c - '1'] = true;
                        cols[y][c - '1'] = true;
                        box[x/3*3+y/3][c-'1'] = true;
                        board[x][y] = c;
                        if (helper(board, rows, cols, box, index + 1)) {
                            return true;
                        }
                        rows[x][c - '1'] = false;
                        cols[y][c - '1'] = false;
                        box[x/3*3+y/3][c-'1'] = false;
                    }
                }
                board[x][y] = '.';
                return false;
            }
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.