Number of Distinct Islands — DFS Shape Hashing

Problem

Count islands with unique shapes. Two islands are the same if one can be translated to equal the other.

Approach — DFS Path Encoding

During DFS, record each direction taken and 'B' (backtrack) when returning. The path string encodes the island's shape independent of position.

Time: O(mn) | Space: O(mn)

Solutions

Python

class Solution:
    def numDistinctIslands(self, grid: list[list[int]]) -> int:
        R,C=len(grid),len(grid[0])
        shapes=set()
        def dfs(r,c,path,d):
            if not(0<=r<R and 0<=c<C) or grid[r][c]!=1: return
            grid[r][c]=0; path.append(d)
            dfs(r+1,c,path,'D'); dfs(r-1,c,path,'U')
            dfs(r,c+1,path,'R'); dfs(r,c-1,path,'L')
            path.append('B')
        for r in range(R):
            for c in range(C):
                if grid[r][c]==1:
                    path=[]
                    dfs(r,c,path,'S')
                    shapes.add(tuple(path))
        return len(shapes)

Complexity

Time: O(mn) | Space: O(mn)