leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

clone-graphV1.py (1221B)

      1 """
      2 # Definition for a Node.
      3 class Node:
      4     def __init__(self, val = 0, neighbors = None):
      5         self.val = val
      6         self.neighbors = neighbors if neighbors is not None else []
      7 """
      8 
      9 from typing import Optional
     10 
     11 
     12 class Solution:
     13     def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
     14         # this is a list of values
     15         # and the corresponding values that it is adjacent to.
     16 
     17         lookup = {}
     18         dfs(node, lookup)
     19 
     20         nodes = {}
     21 
     22         for val in lookup:
     23             nodes[val] = Node(val)
     24 
     25         for val in nodes:
     26             current_node = nodes[val]
     27             for tail_edge in lookup[val]:
     28                 if current_node.neighbors is not None:
     29                     current_node.neighbors.append(nodes[tail_edge])
     30                 else:
     31                     current_node.neighbors = [nodes[tail_edge]]
     32 
     33         return nodes.get(1)
     34 
     35 
     36 def dfs(current_node, lookup):
     37 
     38     if current_node is None or current_node.val in lookup:
     39         return None
     40 
     41     lookup[current_node.val] = []
     42 
     43     if current_node.neighbors is None:
     44         return
     45 
     46     for neighbor in current_node.neighbors:
     47         lookup[current_node.val].append(neighbor.val)
     48         dfs(neighbor, lookup)
     49 
     50     return