Reconstruct Itinerary

Problem: Reconstruct Itinerary

We can do depth-first search start from JFK until we get a valid answer.

Code in Python:

from collections import defaultdict

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        n = len(tickets) + 1

        dict = defaultdict(list)
        for src, dst in tickets:
            dict[src].append(dst)

        res = ["JFK"]
        def depart(src):
            if len(res) == n: return True
            dsts = sorted(dict[src])
            for dst in dsts:
                res.append(dst)
                dict[src].remove(dst)
                if depart(dst): return True
                res.pop()
                dict[src].append(dst)
        depart("JFK")
        return res

During each step of search, we try destinations in lexical order and remove that ticket to avoid duplication.