Valid Sudoku

https://leetcode.com/problems/valid-sudoku/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'.'.

Thoughts

根据sudoku的定义建立三个map, 判断是否在同一行，列还是块。

Code

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Map<Integer, Set<Character>> rows, cols, blks;
        rows = new HashMap<>();
        cols = new HashMap<>();
        blks = new HashMap<>();
        for (int i = 0; i < board.length; i++) {
            rows.put(i, new HashSet<>());
            for (int j = 0; j < board[i].length; j++) {
                char c = board[i][j];
                if (c != '.') {
                    if (rows.get(i).contains(c)) {
                        return false;
                    }
                    rows.get(i).add(c);
                    if (cols.containsKey(j) && cols.get(j).contains(c)) {
                        return false;
                    }
                    if (!cols.containsKey(j)) {
                        cols.put(j, new HashSet<>());
                    }
                    cols.get(j).add(c);

                    int blk = (i / 3) * 3 + j / 3;
                    //System.out.println(blk);
                    if (blks.containsKey(blk) && blks.get(blk).contains(c)) {
                        return false;
                    }
                    if (!blks.containsKey(blk)) {
                        blks.put(blk, new HashSet<>());
                    }
                    blks.get(blk).add(c);
                }
            }
        }

        return true;
    }
}

Analysis

Errors:

1. (i / 3) * 3 和 i并不相等

时空复杂度都是O(n^2).