runtime 15 ms, beats 98.64% of cpp submissions
O(n^2) solution with explanation

tags: none

Valid Sudoku

📖 description

給定一個 9 x 9 的 array 表示一個數獨題目，判斷這個版面是否是一個合法的數獨。

🧠 solution

只需要根據數獨的定義模擬即可，即同一行或列不能出現重複的數字，且畫分的九個區間也不能出現重複的數字。

我們可以利用暴力法去檢查所有狀態，但其實可以藉由把看過的物件儲存起來，來減少搜尋次數到只需要遍歷一次數獨版面。

⏳ time complexity

遍歷一次數獨版面，時間複雜度 O(n^2)
總時間複雜度 O(n^2)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> rows(9,vector<bool>(10,false)),cols(9,vector<bool>(10,false)),blocks(9,vector<bool>(10,false));
        // rows : 第幾列出現過 1~9 哪些數字
        // cols : 第幾行出現過 1~9 哪些數字
        // blocks : 第幾個 block 出現過 1~9 哪些數字

        int curr,blockId;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j] == '.'){
                    continue;
                }
                blockId = (i/3)*3 + j/3;    // 根據當前在數獨版面的位置來決定在第幾個 block
                curr = board[i][j]-'0';     // 當前的數字 (從字元處理成數字)

                // 如果找到重複
                if(rows[i][curr] || cols[j][curr] || blocks[blockId][curr]){
                    return false;
                }

                // 儲存狀態
                rows[i][curr] = true;
                cols[j][curr] = true;
                blocks[blockId][curr] = true;
            }
        }
        return true;
    }
};