LeetCode link

Intuition

  • Using DFS to recursion the path. And build a map that save the dep. and arr. airports. The value in the map is a minHeap to ensure the lexical order.

solution

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    Map<String, PriorityQueue<String>> map;
    public List<String> findItinerary(String[][] tickets) {
        map = new HashMap<>();
        for (String[] ticket: tickets) {
            if (map.containsKey(ticket[0])) {
                map.get(ticket[0]).add(ticket[1]);
            } else {
                PriorityQueue<String> minHeap = new PriorityQueue<>();
                minHeap.add(ticket[1]);
                map.put(ticket[0], minHeap);
            }
        }
        List<String> result = new ArrayList<>();
        result.add("JFK");
        this.helper(result, "JFK", tickets.length);
        return result;
    }
    private boolean helper(List<String> result, String cur, int count) {
        if (count <= 0) {
            return true;
        }
        if (!map.containsKey(cur)) {
            return false;
        }
        PriorityQueue<String> oriHeap = (PriorityQueue)map.get(cur);
        PriorityQueue<String> heap = new PriorityQueue<>(oriHeap);
        while (!heap.isEmpty()) {
            String loc = heap.poll();
            oriHeap.remove(loc);
            result.add(loc);
            if (this.helper(result, loc, count - 1)) {
                return true;
            }
            result.remove(result.size() - 1);
            oriHeap.add(loc);
        }
        return false;
    }
}

promote

  • Can add the airports at last, when the heap is empty, it means the current port is the destination, add it to the path, then jump out this recursion.
  • Each add function in the last of the recursion can add the previous port, so add it to the first place in the path.
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
26
27
28
29
class Solution {
    Map<String, PriorityQueue<String>> map;
    public List<String> findItinerary(String[][] tickets) {
        map = new HashMap<>();
        for (String[] ticket: tickets) {
            if (map.containsKey(ticket[0])) {
                map.get(ticket[0]).add(ticket[1]);
            } else {
                PriorityQueue<String> minHeap = new PriorityQueue<>();
                minHeap.add(ticket[1]);
                map.put(ticket[0], minHeap);
            }
        }
        List<String> result = new LinkedList<>();
        this.helper("JFK", result);
        return result;
    }
    private void helper(String departure, List<String> result) {
        PriorityQueue<String> heap = map.get(departure);
        while (heap != null && !heap.isEmpty()) {
            this.helper(heap.poll(), result);
        }
        ((LinkedList)result).addFirst(departure);
    }
}