LC 0694 [M] Number of Distinct Islands - ALawliet/algorithms GitHub Wiki

it is like number of islands, except we only want the distinct ones, so we use a set and build a key string as we traverse each island

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        def dfs(r, c, area):
            if r < 0 or r >= n_rows or c < 0 or c >= n_cols or grid[r][c] == 0:
                return "0" 
            
            grid[r][c] = 0 # sink island mark visited
            
            u = dfs(r-1, c, area)
            l = dfs(r,  c-1, area)
            d = dfs(r+1, c, area)
            r = dfs(r, c+1, area)
            return u + d + l + r + "1"
        
        distinct = set()
        for r in range(n_rows):
            for c in range(n_cols):
                if grid[r][c] == 1:
                    key = dfs(r, c, "0")
                    # print(key)
                    distinct.add(key)

        return len(distinct)

footer

⚠️ **GitHub.com Fallback** ⚠️