DFS and Union Find solution in Python


  • 0
    S

    First solution use DFS. Second solution use Union Find.

    # Accepted 
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # DFS
        if not len(grid): 
            return 0
        maxRow = len(grid)
        maxCol = len(grid[0])
        visited = [[0 for j in range(maxCol)] for i in range(maxRow)]
        dir = [[0,1],[0,-1],[1,0],[-1,0]]   #direction vector,4 different direciton from (x,y)
    
        def dfs(x, y):
            if x < 0 or y < 0 or x >= maxRow or y >= maxCol:
                return False
            if grid[x][y] == '0' or visited[x][y]:
                return False
            visited[x][y] = 1 
            for direction in dir:
                    dfs(x+direction[0], y + direction[1])
            return True
    
        count = 0 
        for i in range(maxRow):
            for j in range(maxCol):
                    if dfs(i,j):
                        count += 1
        return count
            
    # Accepted 
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        #Union Find
        
        if not len(grid): 
            return 0
        maxRow = len(grid)
        maxCol = len(grid[0])
        id = [i for i in range(maxRow * maxCol)]
        self.count = sum([grid[i][j] == '1'  for i in range(maxRow) for j in range(maxCol) ])
        
        def find(i):
            while i != id[i]:
                id[i] = id[id[i]]
                i = id[i]
            return i
            
        def union(i, j):
            iRoot = find(i)
            jRoot = find(j)
            if iRoot == jRoot:
                return
            else:
                id[iRoot] = jRoot
            self.count -= 1
            
        for i in range(maxRow):
            for j in range(maxCol):
                if grid[i][j] == '0': continue
                curNode = i * maxCol + j 
                if j < maxCol-1 and grid[i][j+1] == '1':
                    union(curNode, curNode + 1)
                if i < maxRow-1 and grid[i+1][j] == '1':
                    union(curNode, curNode + maxCol)
        return self.count

Log in to reply
 

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