Python + JSON + DFS + Beginner Level Solution


  • 0
    R

    I used Python and DFS to get the island coordinates. Then, I subtracted every island that I found and moved it towards to 0,0 coordinate in a tuple. Then, I converted the array into JSON and stored it in a set. At the end, I just get the length of the set and that is the answer.

    
    import json
    
    class Solution(object):
        def numDistinctIslands(self, grid):
    
            setty = set()
            self.tmp = []
            def seeOne(row, col):
                if grid[row][col] != 1:
                    return
                else:
                    self.tmp.append((row,col))
                    grid[row][col] = 0
                    if row -1 >= 0:
                        seeOne(row -1, col)
                    if row + 1 < len(grid):
                        seeOne(row+1, col)
                    if col - 1 >= 0:
                        seeOne(row, col - 1)
                    if col + 1 < len(grid[0]):
                        seeOne(row, col + 1)
            
            def process(tempe):
                xMin = sys.maxint
                yMin = sys.maxint
                for i in tempe:
                    xMin = min(xMin, i[0])
                    yMin = min(yMin, i[1])
                a = []
                
                for i in tempe:
                    a.append((i[0] - xMin, i[1] - yMin))
                self.tmp = a        
            
            for i in xrange(len(grid)):
                for j in xrange(len(grid[0])):
                    if grid[i][j] == 1:
                        seeOne(i, j)
                        process(self.tmp)
                        setty.add(json.dumps(self.tmp))
                        self.tmp = []
            return len(setty)
    

Log in to reply
 

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