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 '.'.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

例子

A partially filled sudoku which is valid.

分析

数独的大小为9x9，可以分成9块，每一块大小为3x3。典型的数独如下图所示：

经典数独

数独的规则：

• 每个横向和纵向行的数字不能重复，必须有且仅有1-9这9个数字；
• 每块的数字不能重复，必须有且仅有1-9这9个数字。

题目要求验证数独的正确性，我们只需要对已有的数字验证上面两条规则就可以了。

要点

• 理解数独的规则；
• 使用unordered_set判断数字是否已经存在。

时间复杂度

O(n^2)，n为数独的大小（长或宽），n一般来说是9

空间复杂度

O(n)

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            unordered_set<char> rs, cs;
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && rs.find(board[i][j]) != rs.end()) return false;
                else rs.insert(board[i][j]);
                if (board[j][i] != '.' && cs.find(board[j][i]) != cs.end()) return false;
                else cs.insert(board[j][i]);
            }
        }
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                unordered_set<char> bs;
                for (int x = 0; x < 3; x++) {
                    for (int y = 0; y < 3; y++) {
                        if (board[i + x][j + y] != '.' && bs.find(board[i + x][j + y]) != bs.end()) return false;
                        else bs.insert(board[i + x][j + y]);
                    }
                }
            }
        }
        return true;
    }
};