Участник:Polina Potapova/reconstruct-itinerary

Материал из DISCOPAL
Перейти к: навигация, поиск

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

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        def depth_first_search(graph, edge, itinerary):            
            while len(graph[edge]) != 0:
                depth_first_search(graph, graph[edge].pop(), itinerary)
            itinerary.append(edge)            
 
        graph = collections.defaultdict(list)
        for departure, arrival in tickets:
            graph[departure].append(arrival)
        for key in graph:
            graph[key].sort()
            graph[key].reverse()
        itinerary = []
        depth_first_search(graph, 'JFK', itinerary)
        answer = itinerary[::-1]
 
        return answer