The journey is actually an Eulerian path. We apply Hierholzer’s algorithm
https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
Iterasive method using stack
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
#Iterasive
#TC: Maximum O(E log E) where E = len(tickes)
#SC: O(E)
Dict = collections.defaultdict(list)
for ele in tickets:
Dict[ele[0]].append(ele[1])
for key in Dict:
Dict[key].sort(reverse = True)
stack = ['JFK']
res = []
while(stack):
start = stack[-1]
if len(Dict[start]) == 0:
res.append(start)
stack.pop()
else:
end = Dict[start][-1]
stack.append(end)
Dict[start].pop()
return res[::-1]
Recursive method using dfs
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
#Recursive
#TC: Maximum O(E log E) where E = len(tickes)
#SC: O(E)
Dict = collections.defaultdict(list)
for ele in tickets:
Dict[ele[0]].append(ele[1])
for key in Dict:
Dict[key].sort(reverse = True)
res = []
def dfs(start):
while(len(Dict[start]) > 0):
end = Dict[start][-1]
Dict[start].pop()
dfs(end)
res.append(start)
dfs('JFK')
return res[::-1]