36. Valid Sudoku

題目網址：https://leetcode.cn/problems/valid-sudoku/

題意：判斷 9 x 9 數獨是否有效, 根據以下規則, 判斷已填入的數字是否有效即可。

• 數字 1 - 9 在每一行只能出現一次
• 數字 1 - 9 在每一列只能出現一次
• 數字 1 - 9 在每一個 3 x 3 九宮格中只能出現一次

空白格以 '.' 表示。

Solution：

想法：一旦 board[r][c] 不為 '.', 就去判斷該 row、col、block 是否有重複的 char

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                const char target = board[r][c];
                if (target == '.') {
                    continue;
                }

                if (!isValidRow(board, r, target)
                    || !isValidCol(board, c, target)
                    || !isValidBlock(board, r, c, target)) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    bool isValidRow(const vector<vector<char>>& board, const int& row, const char& target) {
        bool seen[9] = {false};
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == '.') {
                continue;
            }
            if (seen[board[row][col] - '1']) {
                return false;
            }
            seen[board[row][col] - '1'] = true;
        }
        return true;
    }

    bool isValidCol(const vector<vector<char>>& board, const int& col, const char& target) {
        bool seen[9] = {false};
        for (int row = 0; row < 9; row++) {
            if (board[row][col] == '.') {
                continue;
            }
            if (seen[board[row][col] - '1']) {
                return false;
            }
            seen[board[row][col] - '1'] = true;
        }
        return true;
    }

    bool isValidBlock(const vector<vector<char>>& board, const int& row, const int& col, const char& target) {
        int blockR = (row / 3) * 3;
        int blockC = (col / 3) * 3;
        bool seen[9] = {false};
        for (int r = blockR; r < blockR + 3; r++) {
            for (int c = blockC; c < blockC + 3; c++) {
                if (board[r][c] == '.') {
                    continue;
                }
                if (seen[board[r][c] - '1']) {
                    return false;
                }
                seen[board[r][c] - '1'] = true;
            }
        }
        return true;
    }
};

• time：$O(1)$ ➔ 每個 board[r][c] 判斷該 row、col、block 是否重複皆需 $O(9)$, 故總共需 $O((9 * 9) \cdot (3 * 9))$
• space：$O(1)$ ➔ 只需常數空間