LeetCode Valid Sudoku：三維標記檢查行/列/宮合法性

題目回顧

判斷 9×9 數獨盤面當前狀態是否合法（不要求可解）。空格用 '.' 表示。規則：每行、每列、每 3×3 宮數字 1-9 不重複。

解法：三組標記陣列

• row[9][10]：行標記
• col[9][10]：列標記
• box[9][10]：宮標記，box_idx = (i/3)*3 + j/3

Python 代碼

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                val = board[i][j]
                if val == '.': continue
                if val in rows[i]: return False
                if val in cols[j]: return False
                box_idx = (i // 3) * 3 + j // 3
                if val in boxes[box_idx]: return False
                rows[i].add(val)
                cols[j].add(val)
                boxes[box_idx].add(val)
        return True

C++ 位掩碼優化（更快）

bool isValidSudoku(vector>& board) {
    int rows[9] = {}, cols[9] = {}, boxes[9] = {};
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            char c = board[i][j];
            if (c == '.') continue;
            int bit = 1 << (c - '0');
            int b = (i/3)*3 + j/3;
            if (rows[i] & bit) return false;
            if (cols[j] & bit) return false;
            if (boxes[b] & bit) return false;
            rows[i] |= bit;
            cols[j] |= bit;
            boxes[b] |= bit;
        }
    }
    return true;
}

複雜度

• 時間：O(81) = O(1)
• 空間：O(1) 固定大小數組