Python use one int to hash island, very clean and efficient


  • 0
    G

    Use one int to hash the process of dfs traverse island, just like encode a binary tree, only the shape matters.
    (Python supports arbitrary large number)

    class Solution(object):
        def numDistinctIslands(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            def dfs(i, j, grid):
                if len(grid) > i >= 0 and len(grid[0]) > j >= 0 and grid[i][j] == 1:
                    self.key |= 1
                    self.key <<= 1
                    grid[i][j] = 0
                    dfs(i+1, j, grid)
                    dfs(i-1, j, grid)
                    dfs(i, j+1, grid)
                    dfs(i, j-1, grid)
                else:
                    self.key <<= 1
    
                
            res = set()
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 1:
                        self.key = 0
                        dfs(i, j, grid)
                        res.add(self.key)
            return len(res)
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.