LeetCode 332 Reconstruct Itinerary

#Problem

#⭐️⭐️⭐️⭐️⭐️

Reconstruct Itinerary, if there are more than one path, return lexical order.

#Solution

已经至少是第三遍做这道题了. 从一开始不知所以的乱backtracking到现在一眼看出是一道Euler Path的问题. 还是有一点长进的.

找Euler Path有两种方法:

  1. 最简单直观的就是backtracking, 一条条edge慢慢试，直到找到一条path为止.
  2. Hierholzer’s Algorithm
#Solution #1

自己写的就是backtracking的方法. 详见代码.

#Solution #2

Hierholzer’s Algorithm 是专门用来找Euler Path/Circuit的. Path和Circuit都通用. GeeksforGeeks 有详细的解释和例子.

Hierholzer’s Algorithm看上去既有点像DFS也有点像backtracking, 还有点像topological sort.

根据geeksforgeeks的解释, 它就是一种backtracking的算法. 但是不同于Solution #1中简单粗暴的backtrack, Hierholzer’s Algorithm在走到死路需要backtrack的时候, 可以直接把当前vertex加入到result list里面. 而不是像通常的情况下, 发现这条路行不通然后什么也不用做直接回溯. 根据这一点以及他最后的时间复杂度O(V + E), 我们也可以把它看做是一个简单的DFS甚至有点像topological sort.

至于为什么当发现一条死路的时候可以直接把vertex加入result, 是因为Euler Path的特点. 回想一下判断一个Graph是否有Euler Path的条件:

  1. All vertices have to be in a single Strongly Connected Component.
  2. Only have 0 or 2 odd vertices. (Vertex whose degree is an odd number.)

需要注意一点的是没有人说过这道题的path不能是一个Cycle. 所以odd vertices 0和2都有可能会出现.

但是可以肯定的是, 当你从source出发第一次发现死路的时候, 那个结点确定, 一定, 肯定就是destination. (在cycle的情况下src就是dst). 因为只有两个结点的degree会是奇数. 其他结点如果有一条边进去，就肯定有一条边出来. 因此这就是为什么发现死路之后可以直接把当前结点加入到result list的尾部. 继续回溯之后也是一样, 如果回溯到的结点没有更多的unvisited edges的话, 也就可以加入result list了.

#Performance

Solution #1 的worst case scenario是O( 2^E )

Solution #2 的worst case scenario是O(E + V)

#Notes

有一些Edge case需要注意. 题目并没有说不能有重复的edge. 所以在构建graph的时候adjacency list不能用一个Set来表示. 只能用list或者priority queue. 用List的话构建完graph还需要再把每个adjacency list给sort一遍, 所以还不如用PriorityQueue来的方便.

而且在dfs的过程中, PriorityQueue可以直接弹出下一个需要访问的结点. 甚至都不需要再另外maintain一个visited的data structure!!

#Code

#Solution #1
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;
// 找欧拉path问题！visite each edge exactly once.
// Backtracking
class Solution {
    private class Edge implements Comparable<Edge> {
        String src;
        String dst;
        Edge(final String src, final String dst) {
            this.src = src;
            this.dst = dst;
        }
        @Override
        public int compareTo(final Edge e) {
            return this.dst.compareTo(e.dst);
        }
    }
    public List<String> findItinerary(String[][] tickets) {
        final List<String> res = new ArrayList<>();
        if (tickets == null || tickets.length == 0) return res;
        final Map<String, List<Edge>> graph = new HashMap<>();
        for (final String[] t : tickets) {
            graph.putIfAbsent(t[0], new ArrayList<>());
            graph.putIfAbsent(t[1], new ArrayList<>());
            graph.get(t[0]).add(new Edge(t[0], t[1]));
        }
        for (final String v : graph.keySet()) {
            Collections.sort(graph.get(v));
        }
        final List<Edge> tmp = new ArrayList<>();
        final Set<Edge> visited = new HashSet<>();
        dfs("JFK", tickets.length, graph, visited, res, tmp);
        return res;
    }
    private void dfs(final String v, final int numEdges, final Map<String, List<Edge>> graph,
                     final Set<Edge> visited, final List<String> res, final List<Edge> tmp) {
        if (tmp.size() == numEdges) {
            res.add("JFK");
            for (final Edge e : tmp) {
                res.add(e.dst);
            }
            return;
        }
        for (final Edge e : graph.get(v)) {
            if (!visited.contains(e)) {
                tmp.add(e);
                visited.add(e);
                dfs(e.dst, numEdges, graph, visited, res, tmp);
                if (!res.isEmpty()) return;
                visited.remove(e);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}
#Solution #2
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
// Hierholzer's Algorithm
class Solution {
    public List<String> findItinerary(String[][] tickets) {
        final List<String> res = new LinkedList<>();
        if (tickets == null || tickets.length == 0) return res;
        
        final Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (final String[] t : tickets) {
            graph.putIfAbsent(t[0], new PriorityQueue<>());
            graph.putIfAbsent(t[1], new PriorityQueue<>());
            graph.get(t[0]).offer(t[1]);
        }
        
        dfs("JFK", graph, res);
        return res;
    }
    
    private void dfs(final String v, final Map<String, PriorityQueue<String>> graph, final List<String> res) {
        while (!graph.get(v).isEmpty()) {
            final String adj = graph.get(v).poll();
            dfs(adj, graph, res);
        }
        res.add(0, v);
    }
}

Comments

▲