Solution to LeetCode 332 Reconstruct Itinerary and LeetCode 753 Cracking the Safe.
Hierholzer’s algorithm
Write every combination of length n - “Hamilton Path”, and visit every node exactly once. This is different from “Euler Path”, which is to write every combination of length n-1, and visit every node exactly once. [wiki]
LeetCode 332
Reconstruct Itinerary (Hard). [link]
Hierholzer’s algorithm. Convert the graph to a tree, do post-order traversal, greedily append the child to a list such that the it’s the smallest, and reverse the list after all vertices have been visited.
Time complexity O(m log m) where m is the number of edges. Space complexity O(m). heappop to pop edges, which takes O(log m).
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
que = collections.defaultdict(list)
for frm, to in tickets:
que[frm].append(to) # construct an adjacency list
for key in que:
heapq.heapify(que[key]) # increasing lexical order
def DFS(node):
while que[node]:
tmp = heapq.heappop(que[node])
DFS(tmp)
stack.append(node) # post-order
stack = list()
DFS('JFK') # source
return stack[::-1] # reverse post-order
LeetCode 753
Cracking the Safe (Hard). [link]
The number of all possible passwords is k^n, where k is the number of choices of digit and n is the length of the password. The total lengths for all possible passwords is n* k^n. If every password shares n-1 digits suffix of last node, the total length could reduce to k^n + (n-1).
1] Hierholzer’s algorithm. DFS with backtracking. The idea is to DFS all possible password and collect suffix digits.
Time complexity O(n log n). Space complexity O(n).
class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
res = ["0"] * n # starting node / source
size = k ** n # number of possible passwords
visited = set()
visited.add("".join(res))
if self.dfs(res, visited, size, n, k):
return "".join(res)
return ""
def DFS(self, res, visited, size, n, k):
if len(visited) == size:
return True
node = "".join(res[len(res) - n + 1:]) # slice the final digit
for i in range(k): # consider new digits: 0, 1, 2, ...
node = node + str(i) # append a new digit, "forward"
if node not in visited: # if node is not visited
res.append(str(i)) # append the digit
visited.add(node)
if self.DFS(res, visited, size, n, k):
return True
res.pop() # "backtrack"
visited.remove(node) # "backtrack"
node = node[:-1] # "backtrack"
2] Hierholzer’s algorithm. DFS without backtracking.
