题目描述

解题方法

Solution

from collections import defaultdict
class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        routes = defaultdict(list)
        for s, e in tickets:
            routes[s].append(e)

        def solve(start):
            left, right = [], []
            for end in sorted(routes[start]):
                if end not in routes[start]:
                    continue
                routes[start].remove(end) # delete tickets already visited
                subpathes = solve(end)
                if start in subpathes:
                    left += subpathes
                else:
                    right += subpathes
            return [start] + left + right

        path = solve("JFK")
        return path

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        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]

Reference