Python DFS short solution

  • 23

    Use a dictionary to store the UndirectedGraphNode

    def cloneGraph(self, node):
        if not node:
            return node
        root = UndirectedGraphNode(node.label)
        stack = [node]
        visit = {}
        visit[node.label] = root
        while stack:
            top = stack.pop()
            for n in top.neighbors:
                if n.label not in visit:
                    visit[n.label] = UndirectedGraphNode(n.label)
        return root

  • 0

    What is the running time for this?

  • 5

    Converted your idea into recursive solution:

    class Solution(object):
        def __init__(self):
            self.visited = {}
        def cloneGraph(self, node):
            if not node:
                return None
            if node.label in self.visited:
                return self.visited[node.label]
            clone = UndirectedGraphNode(node.label)
            self.visited[node.label] = clone
            for n in node.neighbors:
            return clone

  • 2

    @autekwing is this solution using DFS? it seems like you are doing BFS since you visit and take care of top's neighbors first and then move on

  • 1

    @ericakimnh It looks like BSF, but he's actually popping from the end of the list, not the head, which makes it DFS. At first I thought it BSF too :)

Log in to reply

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