[Leetcode]332. Reconstruct Itinerary

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        
        _dict=defaultdict(list)
        
        for ticket in sorted(tickets, reverse=True):
            _dict[ticket[0]].append(ticket[1])
        
        plan=[]
        
        def dfs(start):            
            while _dict[start]:
                dest=_dict[start].pop()
                dfs(dest)
            plan.append(start)

        dfs("JFK")        
        return plan[::-1]

References

• https://leetcode.com/problems/reconstruct-itinerary/