332.Reconstruct Itinerary

Tags: [graph], [map], [dfs], [greedy]

Link: https://leetcode.com/problems/reconstruct-itinerary/\#/description

Given a list of airline tickets represented by pairs of departure and arrival airports[from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs fromJFK. Thus, the itinerary must begin withJFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets=[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets=[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution: Graph, DFS, Greedy

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        if not tickets:
            return []

        # build graph
        graph = {}
        for ticket in tickets:
            departure = ticket[0]
            arrival = ticket[1]

            if departure not in graph:
                graph[departure] = [arrival]
            else:
                graph[departure].append(arrival)

        for departure in graph:
            graph[departure].sort()

        itinerary = ['JFK']
        if self.dfs(graph, 'JFK', itinerary):
            return itinerary

        return []

    def dfs(self, graph, departure, itinerary):
        # base case
        if not graph:
            return True

        # index = 0
        # while index < len(graph.get(departure, [])):
        #     arrival = graph[departure][index]

        #     graph[departure].pop(index)
        #     if not graph[departure]:
        #         del graph[departure]

        #     itinerary.append(arrival)
        #     if self.dfs(graph, arrival, itinerary):
        #         return True

        #     itinerary.pop()
        #     if departure not in graph:
        #         graph[departure] = [arrival]
        #     else:
        #         graph[departure].insert(index, arrival)
        #     index += 1

        for i in xrange(len(graph.get(departure, []))):
            arrival = graph[departure][i]

            graph[departure].pop(i)
            if not graph[departure]:
                del graph[departure]

            itinerary.append(arrival)
            if self.dfs(graph, arrival, itinerary):
                return True

            itinerary.pop()
            if departure not in graph:
                graph[departure] = [arrival]
            else:
                graph[departure].insert(i, arrival)

        return False

Revelation:

• Think about each time, we try the smallest lexical Airport code, if dfs cannot traverse all edges, we just let it return false.
• The reason we don't use a visited_edges set is that there exists the scenario that the same departure->arrival can be visited multiple times, such as: [[JFK, ANU], [JFK, TIA], [EZE, AXA], [AXA, TIA], [TIA, ANU], [TIA, ANU], [TIA, JFK], [ANU, EZE], [ANU, JFK], [ANU, TIA]], the [TIA, ANU] got be visited twice.
• The way to trace the edge we visited is that after we visited one edge, we just remove it from the graph.
• In Python, during the list iteration, we can modify the list, we can modify the list, during "for i in xrange(len(arr))" or "for elem in arr", or using the "while loop".

Note:

• Time complexity = O(n) + O(n*nlgn) + O(n!) = O(n!), n is the number of elements of the tickets. Here O(n) is the time complexity to build the graph. O(n*nlgn) is the time complexity of sorting each array in graph, the worst case is that this is a full graph, each node connects to each node, and they are two-directed connected, so there are (n+1) nodes (because there are n tickets), and each node has n edges. O(n!) is the time complexity of this DFS. The worst case is that in the each recursion level the "suitable" "arrival" is always the last element of the graph[departure]. So the first level we need try n times, the next level we need to try (n - 1) times, the third level we need try (n - 2) times... , so the time complexity = O(n * (n - 1) * (n - 2) * ... * 1) = O(n!).