---
# System prepended metadata

title: 'Leetcode [No. 36] Valid Sudoku (MEDIUM) 解題心得'
tags: [leetcode]

---

# Leetcode [No. 36] Valid Sudoku (MEDIUM) 解題心得

+ Neetcode 150 Array & Hash Table
+ Solved on 2024/06/12

## 題目

https://leetcode.com/problems/valid-sudoku/description/

## 思路
+ 這個解法就是一個一個檢查，從檢查row開始，col, SubBoxes
```c++=
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // check each row
        for(int i = 0 ; i < 9; i++)
        {
            unordered_map<char,int> hashMap;
            for(int j = 0 ; j < 9; j++)
            {
                if(board[i][j] != '.')
                {
                    if(hashMap[board[i][j]] > 0)
                    {
                        return false;
                    }
                    else
                    {
                        hashMap[board[i][j]]++;
                    }
                }
            }
        }
        // check each column
        for(int i = 0 ; i < 9; i++)
        {
            unordered_map<char,int> hashMap;
            for(int j = 0 ; j < 9; j++)
            {
                if(board[j][i] != '.')
                {
                    if(hashMap[board[j][i]] > 0)
                    {
                        return false;
                    }
                    else
                    {
                        hashMap[board[j][i]]++;
                    }
                }
            }
        }

        // check each sub-boxes
        for(int i = 0 ; i < 3; i++)
        {
            for(int j = 0 ; j < 3; j++)
            {
                unordered_map<char,int> hashMap;
                for(int k = 0 ; k < 9; k++)
                {
                    if(board[i*3+k/3][j*3+k%3] != '.')
                    {

                        if(hashMap[board[i*3+k/3][j*3+k%3]] > 0)
                        {
                            return false;
                        }
                        else
                        {
                            hashMap[board[i*3+k/3][j*3+k%3]] ++;
                        }
                    }
                    
                }
            }
        }
        return true;
    }
};

```

### 解法分析
+ time complexity: $O(n^2)$


### 執行結果

![image](https://hackmd.io/_uploads/H1YZN4uBA.png)
