694. Number of Distinct Islands - cocoder39/coco39_LC GitHub Wiki

/** WARNING: DO NOT FORGET to add path for backtracking, otherwise, we may have same result when we count two 
     * distinct islands in some cases
     * 
     * eg:              1 1 1   and    1 1 0
     *                  0 1 0          0 1 1
     * with b:          rdbr           rdr
     * without b:       rdr            rdr
     * */

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        seen = set()
        uniqueIslands = set()
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                path = []
                self.getPathSignature(grid, seen, row, col, 'O', path) # origin
                if path:
                    signature = ''.join(path)
                    print(signature)
                    uniqueIslands.add(signature)
        return len(uniqueIslands)
    
    def getPathSignature(self, grid: List[List[int]], seen: Set[tuple[int, int]], row: int, col: int, direction: str, path: List[str]) -> None:
        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
            return
        
        if not grid[row][col] or (row, col) in seen:
            return
        
        seen.add((row, col))
        path.append(direction)
        self.getPathSignature(grid, seen, row-1, col, 'U', path) # up
        self.getPathSignature(grid, seen, row+1, col, 'D', path) # down
        self.getPathSignature(grid, seen, row, col-1, 'L', path) # left
        self.getPathSignature(grid, seen, row, col+1, 'R', path) # right
        path.append('B') # back