Simple Python 169ms


  • 5

    This question is very similar to the Max Area of Island question but here instead of counting the area for each island, we find out the shape of each island.

    The shape of the island can be represented by taking the relative position of the connected cells from the leftmost cell on the top row of the island (the first cell of each island we will visit). For each island we visit, we are guaranteed to visit the top row's leftmost cell first if we iterate the matrix row by row, left to right direction. We will get the same order of cells for islands of the same shape if we perform the search in a consistent manner.

    Here are some examples of how to represent the shape of each island by using cell positions relative to the top left cell.

    # First coordinate is row difference, 
    # Second coordinate is column difference.
    11 -> ((0, 1)) # One cell to the right
    
    11 -> ((0, 1), (1, 1)) # One cell to the right, one cell to the right and bottom
    01
    

    - Yangshun

    class Solution(object):
        def numDistinctIslands(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            island_shapes = set()
            rows, cols = len(grid), len(grid[0])
            def dfs(i, j, positions, rel_pos):
                grid[i][j] = -1
                for direction in ((0, 1), (1, 0), (-1, 0), (0, -1)):
                    next_i, next_j = i + direction[0], j + direction[1]
                    if (0 <= next_i < rows and 0 <= next_j < cols) and grid[next_i][next_j] == 1:
                        new_rel_pos = (rel_pos[0] + direction[0], rel_pos[1] + direction[1])
                        positions.append(new_rel_pos)
                        dfs(next_i, next_j, positions, new_rel_pos)
            for i in range(rows):
                for j in range(cols):
                    if grid[i][j] == 1:
                        positions = []
                        dfs(i, j, positions, (0, 0))
                        island_shapes.add(tuple(positions))
            return len(island_shapes)
    

  • 0
    J

    @yangshun I'm still a bit confused that how you get '11 -> ((1, 0))'. Can you please explain ?


  • 0

    @janusle Sure. 11 means the anchor cell is the left 1, and there is only one cell to the right, which is (0, 1). Sorry I made a mistake and mixed up the coordinates. Have fixed them.


  • 1
    S

    Using frozenset -

    class Solution(object):
        def numDistinctIslands(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """        
            def dfs(current, visited, component, source, m, n):
                i,j = current
                visited[i][j] = True
                component += (i-source[0],j-source[1]),
                for nexti, nextj in  [ (i+x,j+y) for x,y in [ (0,1),(0,-1),(-1,0),(1,0) ] ]:
                    if 0 <= nexti < m and 0 <= nextj < n and visited[nexti][nextj] == False and grid[nexti][nextj] == 1:
                        dfs((nexti,nextj), visited, component, source, m, n)
                        
            
            if not grid:
                return 0
            
            m = len(grid)
            n = len(grid[0])
                    
            visited    = [ [ False for j in range(n) ] for i in range(m)] 
            components = set()
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1 and visited[i][j] == False:
                        component = []
                        dfs( (i,j), visited, component, (i,j), m, n)
                        components.add((frozenset(component)))
            
            return len(components)
    

  • 1
    J

    @yangshun Great! thanks for the solution and explanation.


  • 1
    S

    You dont need to normalize the path by the starting point. Keeping track of the move in the DFS is enough for island signature.

    class Solution:
        def numDistinctIslands(self, grid):
            islands = set([])
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    if grid[i][j] == 1:
                        islands.add(self.dfs(grid, i, j, "s"))
    
            return len(islands)
    
        def dfs(self, g, i, j, path):
            if i < 0 or j < 0 or i >= len(g) or j >= len(g[i]) or g[i][j] == 0:
                return ""
    
            g[i][j] = 0
            return path \
                   + self.dfs(g, i+1, j, "d") + "u" \
                   + self.dfs(g, i-1, j, "u") + "d" \
                   + self.dfs(g, i, j+1, "r") + "l" \
                   + self.dfs(g, i, j-1, "l") + "r"
    

Log in to reply
 

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