LeetCode 36 Valid Sudoku：三維標記數組 O(1) 驗證數獨合法性

題目描述

判斷 9×9 數獨盤面（部分填充，空格為 '.'）是否合法：每行、每列、每個 3×3 子宮內數字 1-9 不重複。僅需驗證已填充部分。

核心思路：三維布爾標記數組

用三個布爾數組記錄「行-數字」、「列-數字」、「宮-數字」是否已出現：

bool row[9][10] = {0}, col[9][10] = {0}, box[3][3][10] = {0};

遍歷盤面，對每個非 '.' 字符 c = board[i][j] - '1' (0-8)：

• 若 row[i][c] || col[j][c] || box[i/3][j/3][c] 已為 true → 非法
• 否則三者均置 true

AC 代碼

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        bool row[9][9] = {}, col[9][9] = {}, box[3][3][9] = {};
        
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                int c = board[i][j] - '1'; // 0-8
                if (row[i][c] || col[j][c] || box[i/3][j/3][c])
                    return false;
                row[i][c] = col[j][c] = box[i/3][j/3][c] = true;
            }
        }
        return true;
    }
};

關鍵點解析

複雜度分析

• 時間：O(81) = O(1) — 固定 9×9 盤面
• 空間：O(9×9 + 9×9 + 3×3×9) = O(1) — 固定大小數組

擴展：位掩碼優化（面試加分項）

用 int 位掩碼替代布爾數組，每行/列/宮用一個 9 位整數：

int row[9] = {}, col[9] = {}, box[9] = {};
for (int i = 0; i < 9; ++i)
    for (int j = 0; j < 9; ++j)
        if (board[i][j] != '.') {
            int bit = 1 << (board[i][j] - '1');
            int b = (i/3)*3 + j/3;
            if (row[i] & bit || col[j] & bit || box[b] & bit) return false;
            row[i] |= bit; col[j] |= bit; box[b] |= bit;
        }

空間更小，位運算極快，展示底層優化能力。

總結

Valid Sudoku 是「固定規模約束滿足問題」驗證的經典例題。三維標記數組或位掩碼均可在一次遍歷中完成所有約束檢查。關鍵在於 box[i/3][j/3] 宮索引計算與字符到下標的映射 ch - '1'。此模式廣泛適用於各類網格約束驗證問題。