ac solution code


  • 0
    /*
         Solution1. DFS. time = O(n) - each node is cloned once; space = O(n)
    
         Steps:
         1. clone each node 
         2. clone each node's neighbors
         Keep the above steps recursively
         
         {0,1,2#1,2#2,2}: #nodeA, NodeA.neighbor0, NodeA.neighbor1,.. #NodeB, NodeB.neighbor0, NodeB.neighbor01
         0: neighbors = 1, 2
         1: neighbors = 2 - because #1, 2 (1's neighbor is 2)
         2: neighbors = 2 - self-cycle
             1
            /  \
           0 -- 2
               /_\
         */
        func cloneGraph1(_ node: UndirectedGraphNode) -> UndirectedGraphNode {
            var map = [UndirectedGraphNode: UndirectedGraphNode]() // map: [original: cloned]
            return DFS(node, &map)
        }
        /// - Returns: the cloned node
        private func DFS(_ original: UndirectedGraphNode, _ map: inout [UndirectedGraphNode: UndirectedGraphNode]) -> UndirectedGraphNode{
            if map.keys.contains(original) {// Visited: Use hashMap to avoid duplicates: Node original was already cloned, return its clone from map hashMap.
                return map[original]!
            }
            // Clone node
            let cloned = UndirectedGraphNode(original.label)
            map[original] = cloned
            cloned.neighbors = [UndirectedGraphNode]()
            // Clone neighbors
            for neighbor in original.neighbors {
                cloned.neighbors.append(DFS(neighbor, &map))
            }
            return cloned
        }
    
        /*Solution2. BFS - O(n) runtime; O(n) space
         
         Steps:
         1. Clone all nodes
         2. Add the cloned nodes' neighbors
         */
        func cloneGraph(_ node: UndirectedGraphNode) -> UndirectedGraphNode {
            var map = [UndirectedGraphNode: UndirectedGraphNode]() // map: [original: cloned]
            var queue = Queue<UndirectedGraphNode>()
            queue.offer(node)
    
            while !queue.isEmpty() {// BFS (queue): Clone nodes
                let count = queue.size
                for _ in 0 ..< count {
                    let original = queue.poll()!
                    if map.keys.contains(original) {// Visited: ignore the node to avoid duplicates
                        continue
                    }
                    // Clone node
                    let cloned = UndirectedGraphNode(original.label)
                    map[original] = cloned
                    for neighbor in original.neighbors {
                        queue.offer(neighbor)
                    }
                }
            }
            // Clone neighbors: add cloned neighbors to cloned node
            for original in map.keys {
                let cloned = map[original]!
                cloned.neighbors = original.neighbors.map{ map[$0]! }// get cloned neighbors in map
            }
            return map[node]!
        }
    
    

    1_1485672873071_DFS.jpg

    0_1485672873067_BFS.jpg


Log in to reply
 

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