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.
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)
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)