Monday, July 21, 2014

Valid Sudoku

Determine if a Sudoku is valid

逐行,逐列,每个小九宫格检查。
public class Solution {
    //Time: O(n^2)  Space: O(n)
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return false;
        }
        
        for (int i = 0; i < 9; i++) {
            boolean[] map = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (!map[board[i][j] - '0']) {
                        map[board[i][j] - '0'] = true;
                    } else {
                        return false;
                    }   
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            boolean[] map = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.') {
                    if (!map[board[j][i] - '0']) {
                        map[board[j][i] - '0'] = true;
                    } else {
                        return false;
                    }   
                }
            }
        }
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                boolean[] map = new boolean[10];
                for (int k = 0; k < 9; k++) {
                    if (board[i + k / 3][j + k % 3] != '.') {
                        if (!map[board[i + k / 3][j + k % 3] - '0']) {
                            map[board[i + k / 3][j + k % 3] - '0'] = true;
                        } else {
                            return false;
                        }
                    }
                }
            } 
        }
        return true;
    }
}

No comments:

Post a Comment