参考了这个视频
把input转换成图的结构。在图上从JKF开始做DFS，remove掉访问过的边，backtrack的时候加回来。 Time = O(n)(建图) + O(nlogn)(排序) + O(n!)(DFS), Space = O(n)
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
List<String> res = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (List<String> ticket : tickets) {
if (!map.containsKey(ticket.get(0))) {
map.put(ticket.get(0), new ArrayList<>());
}
map.get(ticket.get(0)).add(ticket.get(1));
}
for (List<String> list : map.values()) {
Collections.sort(list);
}
String start = "JFK";
res.add(start);
int len = tickets.size() + 1;
if (findItinerary(start, res, map, len)) {
return res;
}
return new ArrayList<>();
}
private boolean findItinerary(String start, List<String> res, Map<String, List<String>> map, int len) {
if (res.size() == len) {
return true;
}
if (!map.containsKey(start)) {
return false;
}
List<String> destinations = map.get(start);
for (int i = 0; i < destinations.size(); i++) {
String destination = destinations.get(i);
destinations.remove(i);
res.add(destination);
if (findItinerary(destination, res, map, len)) {
return true;
}
destinations.add(i, destination);
res.remove(res.size() - 1);
}
return false;
}
}
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices).
Hierholzer Algorithm would compute an Eulerian cycle or path.
Pseudo code:
path = []
DFS(u):
while (u存在未被访问的边e(u,v))
mark边e(u,v)为访问
dfs(v)
end
path.pushLeft(u)
对这道题的分析看这个讲解
Since the problem asks for lexical order smallest solution, we can put the neighbors in a min-heap. In this way, we always visit the smallest possible neighbor first in our trip. link
Time = O(n + nlogn + n), Space = O(n)
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
List<String> res = new ArrayList<>();
Map<String, PriorityQueue<String>> map = new HashMap<>();
for (List<String> ticket : tickets) {
if (!map.containsKey(ticket.get(0))) {
PriorityQueue<String> pq = new PriorityQueue<>();
map.put(ticket.get(0), pq);
}
map.get(ticket.get(0)).offer(ticket.get(1));
}
String start = "JFK";
findItinerary(start, res, map);
return res;
}
private void findItinerary(String start, List<String> res, Map<String, PriorityQueue<String>> map) {
PriorityQueue<String> pq = map.get(start);
while (pq != null && !pq.isEmpty()) {
findItinerary(pq.poll(), res, map); // 从终点开始继续做dfs
}
res.add(0, start); // 当一个点没有任何点可以走的时候，从后(左)加到res
}
}