# 36-Valid Sudoku

###### tags: `Medium`、`Hash_table`
## Question
https://leetcode.com/problems/valid-sudoku/

## Key
Hash table

## Solution
- 我的寫法

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
{
    // Row examination
     for (int row = 0 ; row < 9 ; row ++)
     {
         int [] map = new int[128]; 
            for (int ind = 0; ind < 9 ; ind++ )
         {
            char c = board[row][ind];
            if (c != ".")
            {
                if (map[c] != 0)
                    {
                        return false;
                    }
                else
                    {
                        map[c]++;
                    }                
            }

         }
         
        }   
    // Column examination
     for (int col = 0 ; col < 9 ; col ++)
     {
         int[] map = new int[128]; 
         for (int ind = 0; ind < 9; ind ++ )
         {
            char c = board[col][ind];
            if (c != ".")
            {
                if (map[c] != 0)
                    {
                        return false;
                    }
                else
                    {
                        map[c]++;
                    }                
            }

         }
         
    }   
        // matrix examination  
    for(int m = 0; m < 9; m++)
    {
        int[] map = new int[128]; 
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                c = board[(m/3)*3+i][(m%3)*3+j];
        //每隔三個矩陣使用到的行才會一樣 每三個矩陣使用到的列才會一樣
                if (c != ".")
                {
                    if (map[c] != 0)
                        {
                            return false;
                        }
                    else
                        {
                            map[c]++;
                        }                
                }
            }
        }
    }
};
}

- 大神寫法

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<char,int[3]>num[9]; // used unordered_map's array of 9 size which denote row/column/box  
        
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                char c=board[i][j];
                if(c!='.' &&(num[i][c][0]++>0||num[j][c][1]++>0||num[i/3*3+j/3][c][2]++>0))
                {
                    return false;
                }
            }
        }
        return true;
    }
};

### Python solution
- 大神寫法:

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        
        return self.isRowValid(board) and self.isColValid(board) and self.isSquareValid(board)
    
    def isRowValid(self, board):
        for row in board:
            if not self.isValid(row):
                return False
        return True
    
    def isColValid(self, board):
        for col in zip(*board):
            if not self.isValid(col):
                return False
            
        return True
    
    def isSquareValid(self, board):
        for i in (0, 3, 6):
            for j in (0, 3, 6):
                square = [board[x][y] for x in range(i, i+3) for y in range(j, j+3)]
                if not self.isValid(square):
                    return False
                
        return True
    
    def isValid(self, unit):
        unit = [i for i in unit if i != '.']
        return len(set(unit)) == len(unit)