# 36. Valid Sudoku

## 1.問題 

* 在數獨棋盤中擺位置
  * row中不可有重複數字
  * col中不可有重複數字
  * 3 \* 3的方格中不可有重複數字

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LO31dR2btZ-Rgp5Y5az%2F-LO33hOfyNg4xRC4PhYS%2F20181005.jpg?alt=media\&token=ebd2cebd-c516-41c5-88d3-27a841674471)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 時間複雜度與可用空間是否有限制?&#x20;
* function header, parameter
* test input
* 說明想法
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                if (!isValidWindow(board, i * 3, j * 3)) {
                    return false;
                }
            }
        }
        for (int i = 0; i < 9; i++){
            if (!isValidRow(board, i)) {
               return false;
            }
            if (!isValidCol(board, i)) {
               return false;
            }
        }
        return true;
    }
private:
    bool isValidWindow(vector<vector<char>> board, int startX, int startY) {
        vector<int> window(10, 0);
        for (int i = startX; i < startX + 3; i++) {
            for (int j = startY; j < startY +3; j++) {
                int index = int(board[i][j] - '0');
                if(index <= 9 && index >= 1) {   
                    if (window[index]) {
                        return false;
                    } else {
                        window[index]++;
                    }
                }
            }
        }
        return true;
    }
    
    bool isValidRow(vector<vector<char>> board, int start) {
        vector<int> window(10, 0);
        for (int i = 0; i < 9; i++) {
            int index = int(board[start][i] - '0');
            if(index <= 9 && index >= 1) {   
                if (window[index]) {
                    return false;
                } else {
                    window[index]++;
                }
            }
        }
        
        return true;
    }
    
    bool isValidCol(vector<vector<char>> board, int start) {
        vector<int> window(10, 0);
        for (int i = 0; i < 9; i++) {
            int index = int(board[i][start] - '0');
            if(index <= 9 && index >= 1) {   
                if (window[index]) {
                    return false;
                } else {
                    window[index]++;
                }
            }
        }
        
        return true;
    }
};
```