[Leetcode][python]36. Valid Sudoku

 

problem:

 

code :

from collections import defaultdict

# dictionay = hashmap
# multiple values -> defaultdictionary

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 3 Hashmaps
        # - Key : row
        # - Key : column
        # - Key : 9 section
            # hash function to get key with (row, column)
            # key = 3*int(row/3) + column//3
        rowHash = defaultdict()
        colHash = defaultdict()
        secHash = defaultdict()
        
        # hashFunction    
        def getKey(row :int, column :int) -> int :
            key = 3*int(row/3) + column//3
            print(f'row,column:{row},{column} key:{key}')
            return key
        
        #traversal
        for r in range(len(board)) :
            for c in range(len(board[r])) :
                # 1.check dot
                if board[r][c] == '.':
                    continue
                    
                number = board[r][c]
                
                # 2. check row
                if r in rowHash:
                    if number in rowHash[r]:
                        print(f'{r},{c} key:{r}')
                        return False
                rowHash.setdefault(r, []).append(number) #key: r
                
                # 3. check column
                if c in colHash:
                    if number in colHash[c]:
                        print(f'{r},{c} key:{c}')
                        return False
                colHash.setdefault(c, []).append(number) #key: c
                
                # 4. check section
                key = getKey(r,c)
                if key in secHash:
                    if number in secHash[key]:
                        print(f'{r},{c} key:{key}')
                        return False
                secHash.setdefault(key, []).append(number) #key: return value of getKey method
                    
        return True

 

output : false

expected : true

stdout : 4,0 key:1.3333333333333333

[[".","8","7","6","5","4","3","2","1"],

["2",".",".",".",".",".",".",".","."],

["3",".",".",".",".",".",".",".","."],

["4",".",".",".",".",".",".",".","."],

["5",".",".",".",".",".",".",".","."],

["6",".",".",".",".",".",".",".","."],["7",".",".",".",".",".",".",".","."],["8",".",".",".",".",".",".",".","."],["9",".",".",".",".",".",".",".","."]]

 

Explanation : 

Create 3 kind of hashmap to examin this number is already exist

3 kind of hashmap means 3 different of keys : row, column, section

row and column hashmap is easy to get key 

but for the section key, I created hash function : row will be more weighted 

to get key, first divide row by 3 and multiple 3 times and use reminder divided by 3

 

*One thing that I should care of is when you divide number in python they will return me float number not integer type.

So I need to convert it to Integer.