Skip to content

332. Reconstruct Itinerary

  • Time: $O(|E|\log |E|)$
  • Space: $O(|E|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  vector<string> findItinerary(vector<vector<string>>& tickets) {
    vector<string> ans;
    unordered_map<string, multiset<string>> graph;

    for (const vector<string>& ticket : tickets)
      graph[ticket[0]].insert(ticket[1]);

    dfs(graph, "JFK", ans);
    reverse(begin(ans), end(ans));
    return ans;
  }

 private:
  void dfs(unordered_map<string, multiset<string>>& graph, const string& u,
           vector<string>& ans) {
    while (graph.count(u) && !graph[u].empty()) {
      const string v = *begin(graph[u]);
      graph[u].erase(begin(graph[u]));
      dfs(graph, v, ans);
    }
    ans.push_back(u);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public List<String> findItinerary(List<List<String>> tickets) {
    LinkedList<String> ans = new LinkedList<>();
    Map<String, Queue<String>> graph = new HashMap<>();

    for (final List<String> ticket : tickets) {
      graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
      graph.get(ticket.get(0)).offer(ticket.get(1));
    }

    dfs(graph, "JFK", ans);
    return ans;
  }

  private void dfs(Map<String, Queue<String>> graph, final String u, LinkedList<String> ans) {
    final Queue<String> arrivals = graph.get(u);
    while (arrivals != null && !arrivals.isEmpty())
      dfs(graph, arrivals.poll(), ans);
    ans.addFirst(u);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def findItinerary(self, tickets: List[List[str]]) -> List[str]:
    ans = []
    graph = collections.defaultdict(list)

    for a, b in reversed(sorted(tickets)):
      graph[a].append(b)

    def dfs(u: str) -> None:
      while u in graph and graph[u]:
        dfs(graph[u].pop())
      ans.append(u)

    dfs('JFK')
    return ans[::-1]