首页 > itarticle > [leetcode] problem 332 – reconstruct itinerary

[leetcode] problem 332 – reconstruct itinerary

admin 11月 13, 2020 0

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 from JFK. Thus, the itinerary must begin with JFK.

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

No.1

Input: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]

Output: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

No.2

Input: [[“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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
public List<String> (List<List<String>> tickets) {
    List<String> result = new ArrayList<>();
    Map<String, PriorityQueue<String>> map = new HashMap<>();

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

    dfs(result, map, "JFK");
    Collections.reverse(result);
    return result;
}

private void dfs(List<String> result, Map<String, PriorityQueue<String>> map, String departure) {
    while (map.containsKey(departure) && !map.get(departure).isEmpty()) {
        String arrival = map.get(departure).poll();
        dfs(result, map, arrival);
    }

    result.add(departure);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能