Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:


       If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
       All airports are represented by three capital letters (IATA code).
       You may assume all tickets form at least one valid itinerary.


Example 1:


Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]


Example 2:


Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.


Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Difficulty: interview

Starter code:

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        

Solutions:
from collections import defaultdict
 
 class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         
         graph = defaultdict(list)
         for from_, to_ in tickets:
             graph[from_].append(to_)
         
         for each in graph:
             graph[each].sort()
         
         res = []
         self.dfs(graph, "JFK", res)
         return res[::-1]
     
     
     def dfs(self, graph, from_, results):
         
         while graph[from_]:
             curr = graph[from_].pop(0)
             self.dfs(graph, curr, results)
         
         results.append(from_)

class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         dict = collections.defaultdict(list)
         for flight in sorted(tickets)[::-1]:
             dict[flight[0]].append(flight[1])
         res = collections.deque()
         
         def visit(s):
             while dict[s]:
                 visit(dict[s].pop())
             res.appendleft(s)
         visit("JFK")
         return list(res)

class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         targets = collections.defaultdict(list)
         for a, b in sorted(tickets, reverse=True):
             targets[a] += [b]
         route, stack = [], ['JFK']
         
         while stack:
             while targets[stack[-1]]:
                 stack += [targets[stack[-1]].pop()]
             route += [stack.pop()]
         return route[::-1]


class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         graph = {}
         for line in tickets:
             if line[0] not in graph:
                 graph[line[0]] = [line[1]]
             else:
                 graph[line[0]].append(line[1])
         for key in graph:
             graph[key] = sorted(graph[key], reverse = True)
         
         res = []
         cur = "JFK"
         stack = []
         for i in range(len(tickets)):
             while (cur not in graph) or (not graph[cur]):
                 stack.append(cur)
                 cur = res.pop()   
             res.append(cur)
             cur = graph[cur].pop()
             
         res.append(cur)
         while stack:
             res.append(stack.pop())
         return res
             
             


from collections import deque, defaultdict
 import heapq
 
 class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         edges = defaultdict(list)
         for ticket in tickets:
             heapq.heappush(edges[ticket[0]], ticket[1])
         order = deque([])
         self.dfs(order, edges, 'JFK')
         return list(order)
     
     def dfs(self, order, edges, city):
         while edges[city]:
             next_city = heapq.heappop(edges[city])
             self.dfs(order, edges, next_city)
         order.appendleft(city)
         

from heapq import *
 class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         import collections
         targets=collections.defaultdict(list)
         for a,b in sorted(tickets):
             targets[a]+=b,
         # for key in targets:
         #     heapify(targets[key])
         res=[]
         self.visit('JFK',res, targets)
         return res[::-1]
     
     def visit(self,airport, res, targets):
         while targets[airport]:
             self.visit(targets[airport].pop(0),res,targets)
         res.append(airport)

class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         tickets.sort()
         schedule = {}
         for ticket in reversed(tickets):
             schedule[ticket[0]] = schedule[ticket[0]] + [ticket[1]] if ticket[0] in schedule else [ticket[1]]
         return list(reversed(self.fly(schedule, "JFK")))
         
     def fly(self, schedule, depart):
         route = []
         while depart in schedule and len(schedule[depart]) > 0:
             route += self.fly(schedule, schedule[depart].pop())
         route += [depart]
         return route

class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         self.hasmap = {}
         for ticket in tickets:
             self.hasmap.setdefault(ticket[0], []).append(ticket[1])
         self.route = ['JFK']
         return self.dfs('JFK', tickets)
     
     def dfs(self, start_airport, tickets):
         if len(self.route) == len(tickets) + 1:
             return self.route
         
         # sort destination by legixal order
         # See one case that there is destination but not in the hashmap dictionary
         dests =self.hasmap.get(start_airport)
         if dests is not None:
             for dest in sorted(dests):
                 self.hasmap[start_airport].remove(dest)
                 self.route.append(dest)
                 work = self.dfs(dest, tickets)
                 if work:
                     return self.route
                 self.route.pop()
                 # add it back
                 self.hasmap[start_airport].append(dest)

from collections import deque
 from collections import defaultdict
 class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         d = defaultdict(list)
         for flight in tickets:
             d[flight[0]] += flight[1],
         self.route = ["JFK"]
         def dfs(start = 'JFK'):
             if len(self.route) == len(tickets) + 1:
                 return self.route
             myDsts = sorted(d[start])
             for dst in myDsts:
                 d[start].remove(dst)
                 self.route += dst,
                 worked = dfs(dst)
                 if worked:
                     return worked
                 self.route.pop()
                 d[start] += dst,
         return dfs()      
         

class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         
         d = collections.defaultdict(list)
         tickets.sort(key = operator.itemgetter(1)) 
         
         for src, dst in tickets:
             d[src].append([dst, False])
             
         ans = []
             
         def DFS(src):
             
             ans.append(src)
          
             if len(ans) == len(tickets)+1: return True
             
             for i, a in enumerate(d[src]):
             
                 if not a[1]:
                     d[src][i][1] = True
                
                     if DFS(a[0]):
                         return True
                     d[src][i][1] = False
             ans.pop()
             return False
             
         DFS('JFK')
         return ans
         
                     


class Solution(object):
 
     def __init__(self):
         self.res = []
 
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         if tickets is None or len(tickets) == 0:
             return []
 
         dic = {}
         dic_city = {}
         for t in tickets:
             if (t[0], t[1]) not in dic:
                 dic[(t[0], t[1])] = 0
             dic[(t[0], t[1])] += 1
             if t[0] not in dic_city:
                 dic_city[t[0]] = []
             dic_city[t[0]].append(t[1])
         for k in dic_city.keys():
             dic_city[k] = set(dic_city[k])
             dic_city[k] = list(dic_city[k])
             dic_city[k].sort()
         self.res = []
         self.dfs("JFK", dic, dic_city, ["JFK"], len(tickets)+1)
         return self.res
 
     def dfs(self, city, dic, dic_city, cur, tar):
         if len(cur) == tar:
             if not self.res:
                 self.res = list(cur)
             
             return True
         if city in dic_city:
             citys = dic_city[city]
             for c in citys:
                 if (city, c) in dic and dic[(city, c)]>0:
                     dic[(city, c)]-=1
                     cur.append(c)
                     if self.dfs(c, dic, dic_city, cur, tar):
                         return True
                     cur.pop()
                     dic[(city, c)]+=1
         return False

class Solution:
     def findItinerary(self, tickets):
         """
         :type tickets: List[List[str]]
         :rtype: List[str]
         """
         d = collections.defaultdict(list)
         tickets.sort()
         for i,j in tickets:
             d[i] += [j]
             
         def dfs(path, start):
             path += [start]
             if len(path) == length:
                 return True
             i = 0
             while i <len(d[start]):
                 next = d[start].pop(0)
                 print((next, d[start]))
                 i += 1
                 if dfs(path, next):
                     return True
                 d[start] += [next]
             path.pop()
             return False    
                 
         path, length = [], len(tickets) + 1
         dfs(path, 'JFK')
         return path