Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/332.html

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". 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"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

 

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

 

Constraints:

  • 1 <= tickets.length <= 300
  • tickets[i].length == 2
  • fromi.length == 3
  • toi.length == 3
  • fromi and toi consist of uppercase English letters.
  • fromi != toi

Algorithm

First of all, the graph is established, through the adjacency linked list.

Since the problem requires the solution to be small in alphabetical order, then we consider using multiset, which can be automatically sorted.

After our graph is built, we start traversal from node JFK. As long as there is a node in the multiset mapped by the current node, we take this node out, delete it in the multiset, and then continue to recursively traverse this node.

Finally, the order of our results is the opposite of what we need, we will flip it again at the end.

Code

  • import java.util.*;

public class Reconstruct_Itinerary {

    public static void main(String[] args) {
        Reconstruct_Itinerary out = new Reconstruct_Itinerary();
        Solution s = out.new Solution();

        System.out.println(s.findItinerary(Arrays.asList(
            Arrays.asList("JFK","SFO"),
            Arrays.asList("JFK","ATL"),
            Arrays.asList("SFO","ATL"),
            Arrays.asList("ATL","JFK"),
            Arrays.asList("ATL","SFO")
        )));
    }


    public class Solution {
        public List<String> findItinerary(List<List<String>> tickets) {

            List<String> result = new ArrayList<>();

            if (tickets == null || tickets.size() == 0) {
                return result;
            }

            // step 1: build the ajdList
            // start => list of destinations
            Map<String, List<String>> adjList = new HashMap<>();
            for (List<String> ticket : tickets) {
                String from = ticket.get(0);
                String to = ticket.get(1);

                if (adjList.containsKey(from)) {
                    adjList.get(from).add(to);
                } else {
                    List<String> neighbors = new ArrayList<>();
                    neighbors.add(to);
                    adjList.put(from, neighbors);
                }
            }

            // step 2: sort the adjlist according to lex order
            for (String from : adjList.keySet()) {
                List<String> neighbors = adjList.get(from);
                Collections.sort(neighbors);
            }

            // step 3: start the dfs
            findItineraryDfs("JFK", adjList, result);

            return result;
        }

        private void findItineraryDfs(String curr, Map<String, List<String>> adjList, List<String> result) {

            List<String> neighbors = adjList.get(curr);

            if (neighbors != null) {
                while (neighbors.size() > 0) {
                    String neighbor = neighbors.get(0); // get first one, lex order
                    neighbors.remove(0); // @note: here is the duplicate removal part, next recursion will not have this neighbour

                    findItineraryDfs(neighbor, adjList, result);
                }
            }

            result.add(0, curr);
        }
    }
}

public class Solution_lambda_dfs {

    // default heap order is min-at-top, so ensure lexical order of result
    Map<String, PriorityQueue<String>> targets = new HashMap<>();
    List<String> route = new LinkedList<>();

    // Java Lambda
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> targets = new HashMap<>();
        for (List<String> ticket : tickets)
            targets.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
        dfs("JFK");
        return route;
    }

    void dfs(String airport) {
        while (targets.containsKey(airport) && !targets.get(airport).isEmpty())
            dfs(targets.get(airport).poll());
        route.add(0, airport);
    }

}


  • // OJ: https://leetcode.com/problems/reconstruct-itinerary/
// Time: O(E^2)
// Space: O(E)
class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& E) {
        int N = E.size();
        vector<bool> used(N);
        unordered_map<string, vector<pair<string, int>>> G;
        for (int i = 0; i < E.size(); ++i) G[E[i][0]].emplace_back(E[i][1], i);
        for (auto &[u, vs] : G) sort(begin(vs), end(vs));
        vector<string> path{"JFK"};
        function<bool()> dfs = [&]() {
            if (path.size() == N + 1) return true;
            for (auto &[v, index] : G[path.back()]) {
                if (used[index]) continue;
                used[index] = true;
                path.push_back(v);
                if (dfs()) return true;
                path.pop_back();
                used[index] = false;
            }
            return false;
        };
        dfs();
        return path;
    }
};

  • from collections import deque


class Solution(object):
  def findItinerary(self, tickets):
    """
    :type tickets: List[List[str]]
    :rtype: List[str]
    """
    graph = {}
    hashset = set([])
    for ticket in tickets:
      graph[ticket[0]] = graph.get(ticket[0], []) + [ticket[1]]

    maxLen = len(tickets) + 1

    for k in graph:
      graph[k] = deque(sorted(graph[k]))

    def dfs(path, graph, maxLen, start):
      if len(path) == maxLen:
        return path + []
      for k in range(0, len(graph.get(start, []))):
        nbr = graph.get(start, [])
        top = nbr.popleft()
        path.append(top)
        ret = dfs(path, graph, maxLen, top)
        if ret:
          return ret
        path.pop()
        nbr.append(top)
      return []

    return dfs(["JFK"], graph, maxLen, "JFK")

All Problems

All Solutions