重新安排行程

The solution uses a depth-first search (DFS) combined with a min-heap for lexical order and a stack to build the itinerary. Initially, it constructs a graph with directed edges from each ticket's departure to its destination, using a defaultdict of lists. Each list is then converted into a min-heap to ensure that the next destination selected is the lexicographically smallest available. Starting from 'JFK', the DFS explores as far as possible along each branch, pushing the airports to the stack once all possible paths from that airport are exhausted. After the DFS completes, the stack holds the itinerary in reverse order, which is then reversed to produce the final itinerary order. This approach inherently handles the backtracking by exploring all possible routes using each ticket exactly once.

时间复杂度: O(E log m)

空间复杂度: O(V + E)

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        import collections
        import heapq  # Used for maintaining a min-heap
        self.ans = None  # Not used, can be removed
        maps = collections.defaultdict(list)  # Graph representation
        for a, b in tickets:
            maps[a].append(b)  # Fill adjacency list
        for k in maps:
            heapq.heapify(maps[k])  # Heapify each destination list
        
        def dfs(cur):
            while maps[cur]:
                tmp = heapq.heappop(maps[cur])  # Always choose lexicographically smallest airport
                dfs(tmp)  # Recursively travel to the next airport
            stack.append(cur)  # Add airport to stack after visiting all possible next airports
        
        stack = []
        dfs('JFK')  # Start DFS from 'JFK'
        return stack[::-1]  # Return reversed stack as the final itinerary