Got LTE in python, but accepted in C++... Anyone can improve the efficiency of my python code?


  • 0
    Z

    I devised a two-pass procedures to solve this problem, using hash map and BFS.

    1. BFS the graph from the given node. For each node n, clone it as new node m, and set map map[n]=m.

    2. For each n in map's keys, we update the neighbor relationships. For each neighbor nn in n.neighbors, we have mm=map[nn] then we add mm into map[n].neighbors.

    The pseudo-code, python code, and C++ code can be found in my blog here. However, I only paste my python code here. I tried python first and got LTE, then I translated the python code into C++ using <vector> and <map>, finally got accepted.

    Can anyone help me with improving my python code below? THANKS!

    # Definition for a undirected graph node
    # class UndirectedGraphNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.neighbors = []
     
    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            """
            Similar to the previous problem "Copy List with Random Pointer"
            which deepcopies a list node containing (value, next, random).
            So we can use similar technique.
            We need to assume that each node has a path to the given node
            """
            # Special case:
            if node is None:
                return None
             
            # We use a dictionary to map between the original node and its copy
            # Also, we can use mapping.keys() to keep track the nodes we already visited
            mapping = {}
             
            # BFS from the given node
            q = [node]
            while q:
                # I do not pop/push on q, since it is not efficient for python build-in list structure
                # Instead, I just create a new empty list, and iterate all elements in q
                # After adding all neighbors to new_q, set q = new_q
                new_q = []
                for n in q:
                    # Clone n and map it with its clone
                    mapping[n] = UndirectedGraphNode(n.label)
                    # Check its neighbors
                    for x in n.neighbors:
                        if x not in mapping.keys():
                            new_q.append(x)
                q = new_q
             
            # All nodes are mapping.keys()
            for n in mapping.keys():
                for x in n.neighbors:
                    mapping[n].neighbors.append(mapping[x])
             
            # Return the clone of node
            return mapping[node]
            
    

  • 1
    X

    I think your code does not deal with multigraph problem and hence the "new_q" has many identical nodes.

    A slightly modified version of your code works:

            if(node==None):return None
            mapper={};
            qlist={node:1}
            while (len(qlist)>0):
                    qlist2={};
                    for key in qlist:qlist2[key]=qlist[key]
                    for x in qlist2:
                            mapper[x]=UndirectedGraphNode(x.label)
                            for y in x.neighbors:
                                    if(not(y in mapper)):qlist[y]=1 # works
                            del qlist[x]
            for key in mapper:
                    node2=mapper[key]
                    for x in key.neighbors:
                            node2.neighbors+=[mapper[x]]
            return mapper[node]`        def cloneGraph(self, node):
            if(node==None):return None
            mapper={};
            qlist={node:1}
            while (len(qlist)>0):
                    qlist2={};
                    for key in qlist:qlist2[key]=qlist[key]
                    for x in qlist2:
                            mapper[x]=UndirectedGraphNode(x.label)
                            for y in x.neighbors:
                                    if(not(y in mapper)):qlist[y]=1 # works
                            del qlist[x]
            for key in mapper:
                    node2=mapper[key]
                    for x in key.neighbors:
                            node2.neighbors+=[mapper[x]]
            return mapper[node]

Log in to reply
 

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