4-7 lines Python, ~7 lines C++/Java


  • 2

    The Good

    def cloneGraph(self, node):
        memo = {}
        def clone(node):
            if node not in memo:
                c = memo[node] = UndirectedGraphNode(node.label)
                c.neighbors = map(clone, node.neighbors)
            return memo[node]
        return node and clone(node)
    

    The Bad

    def cloneGraph(self, node, memo={None: None}):
        if node not in memo:
            c = memo[node] = UndirectedGraphNode(node.label)
            c.neighbors = map(self.cloneGraph, node.neighbors)
        return memo[node]
    

    The OJ accepts it, but it's kinda unclean (added a default argument) and unsafe (memo is reused from one test case to the next).


    The Ugly

    Java:

    public class Solution {
        Map<Object,UndirectedGraphNode> clone = new HashMap<Object,UndirectedGraphNode>();
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node != null && !clone.containsKey(node)) {
                clone.put(node, new UndirectedGraphNode(node.label));
                for (UndirectedGraphNode n : node.neighbors)
                    clone.get(node).neighbors.add(cloneGraph(n));
            }
            return clone.get(node);
        }
    }
    

    C++:

    class Solution {
        unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> clone;
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if (node && !clone[node]) {
                clone[node] = new UndirectedGraphNode(node->label);
                for (auto n : node->neighbors)
                    clone[node]->neighbors.push_back(cloneGraph(n));
            }
            return clone[node];
        }
    };
    

    Would also be a bit unsafe if the OJ didn't create a new Solution object for each test case (I think it does). If necessary, I'd outsource the current cloneGraph code into a helper and in cloneGraph I'd initialize the map and then call the helper.

    And yes, joke's on me. After calling my Python solutions "good" and "bad", I decided to create an "ugly" one. So, naturally, I wrote one in Java. Unfortunately (?), it turned out to be not so ugly after all. Neither did the C++ version.


  • 0
    O

    Hey, I wander how the return statement "return node and clone(node)" work,
    it seems equal to "return clone(node) if node else None", but I don't understand why.
    And how do you work with recursive problem? You always make recursive problem being solved elegantly and concisely, how do u do that!! Thank you!


  • 0

    Not sure how to answer. That's just what and does. It's a boolean "and", returning a boolean value, in Python in the form of the appropriate one of its two arguments. Quote from the docs:

    The expression x and y first evaluates x; if x is false, its value is returned; otherwise, y is evaluated and the resulting value is returned.

    About recursion, I guess that's just experience, and trying hard to make it as elegant as I can.


Log in to reply
 

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