*694 Number of Distinct Islands

https://leetcode.com/problems/number-of-distinct-islands/

solution

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        def depth_first_search(i: int, j: int, move: int):
            grid[i][j] = 0
            path.append(str(move)) 
           
            directions = (-1, 0, 1, 0, -1)            
            for h in range(4):                
                x, y = i + directions[h], j + directions[h+1]                
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    depth_first_search(x, y, h+1)
            path.append(str(-move))  # Add the reverse move to path to differentiate shapes

        paths = set()
        path = []
        m, n = len(grid), len(grid[0])

        for i, row in enumerate(grid):
            for j, value in enumerate(row):
                if value:
                    depth_first_search(i, j, 0)
                    paths.add("".join(path))
                    path.clear()

        return len(paths)

时间复杂度：O(m * n) 空间复杂度：O()

follow up

652. Find Duplicate Subtrees

711. Number of Distinct Islands II