M-332. Reconstruct Itinerary

Loading...LeetCode

# 脑壳疼
# https://leetcode.com/problems/reconstruct-itinerary/discuss/78768/Short-Ruby-Python-Java-C%2B%2B
# 1
from heapq import heappop, heappush
from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        tree = defaultdict(list)
        for start, dest in tickets:
            heappush(tree[start], dest)
        res = []
        def dfs(start):
            while tree[start]:
                dest = heappop(tree[start])
                dfs(dest)
            res.append(start)
        dfs('JFK')
        return res[::-1]

# 2
class Solution:
    def findItinerary(self, tickets):
        targets = collections.defaultdict(list)
        for a, b in sorted(tickets)[::-1]:
            targets[a] += b,
        route = []
        def visit(airport):
            while targets[airport]:
                visit(targets[airport].pop())
            route.append(airport)
        visit('JFK')
        return route[::-1]