332. Reconstruct Itinerary

  • 28.4%

https://leetcode.com/problems/reconstruct-itinerary/#/description

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.
1
2
3
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
1
2
3
4
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c

Short Ruby / Python / Java / C++

Just Eulerian path. Greedy DFS, building the route backwards when retreating.

More explanation and example under the codes.

Iterative versions inspired by fangyang (I had only thought of recursion, d’oh).

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findItinerary(self, tickets):
targets = collections.defaultdict(list)
for a, b in sorted(tickets)[::-1]:
targets[a] += b,
route = []
def visit(airport):
while targets[airport]:
visit(targets[airport].pop())
route.append(airport)
visit('JFK')
return route[::-1]
Iterative version:

def findItinerary(self, tickets):
targets = collections.defaultdict(list)
for a, b in sorted(tickets)[::-1]:
targets[a] += b,
route, stack = [], ['JFK']
while stack:
while targets[stack[-1]]:
stack += targets[stack[-1]].pop(),
route += stack.pop(),
return route[::-1]

Java

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
public List<String> findItinerary(String[][] tickets) {
for (String[] ticket : tickets)
targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
visit("JFK");
return route;
}

Map<String, PriorityQueue<String>> targets = new HashMap<>();
List<String> route = new LinkedList();

void visit(String airport) {
while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
visit(targets.get(airport).poll());
route.add(0, airport);
}
Iterative version:

public List<String> findItinerary(String[][] tickets) {
Map<String, PriorityQueue<String>> targets = new HashMap<>();
for (String[] ticket : tickets)
targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
List<String> route = new LinkedList();
Stack<String> stack = new Stack<>();
stack.push("JFK");
while (!stack.empty()) {
while (targets.containsKey(stack.peek()) && !targets.get(stack.peek()).isEmpty())
stack.push(targets.get(stack.peek()).poll());
route.add(0, stack.pop());
}
return route;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<string> findItinerary(vector<pair<string, string>> tickets) {
for (auto ticket : tickets)
targets[ticket.first].insert(ticket.second);
visit("JFK");
return vector<string>(route.rbegin(), route.rend());
}

map<string, multiset<string>> targets;
vector<string> route;

void visit(string airport) {
while (targets[airport].size()) {
string next = *targets[airport].begin();
targets[airport].erase(targets[airport].begin());
visit(next);
}
route.push_back(airport);
}

Explanation

First keep going forward until you get stuck. That’s a good main path already. Remaining tickets form cycles which are found on the way back and get merged into that main path. By writing down the path backwards when retreating from recursion, merging the cycles into the main path is easy - the end part of the path has already been written, the start part of the path hasn’t been written yet, so just write down the cycle now and then keep backwards-writing the path.

Example:

enter image description here

From JFK we first visit JFK -> A -> C -> D -> A. There we’re stuck, so we write down A as the end of the route and retreat back to D. There we see the unused ticket to B and follow it: D -> B -> C -> JFK -> D. Then we’re stuck again, retreat and write down the airports while doing so: Write down D before the already written A, then JFK before the D, etc. When we’re back from our cycle at D, the written route is D -> B -> C -> JFK -> D -> A. Then we retreat further along the original path, prepending C, A and finally JFK to the route, ending up with the route JFK -> A -> C -> D -> B -> C -> JFK -> D -> A.


https://discuss.leetcode.com/topic/36721/short-c-dfs-iterative-44ms-solution-with-explanation-no-recursive-calls-no-backtracking

Short C++ DFS iterative 44ms solution with explanation. No recursive calls, no backtracking.

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
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
// Each node (airport) contains a set of outgoing edges (destination).
unordered_map<string, multiset<string>> graph;
// We are always appending the deepest node to the itinerary,
// so will need to reverse the itinerary in the end.
vector<string> itinerary;
if (tickets.size() == 0){
return itinerary;
}
// Construct the node and assign outgoing edges
for (pair<string, string> eachTicket : tickets){
graph[eachTicket.first].insert(eachTicket.second);
}
stack<string> dfs;
dfs.push("JFK");
while (!dfs.empty()){
string topAirport = dfs.top();
if (graph[topAirport].empty()){
// If there is no more outgoing edges, append to itinerary
// Two cases:
// 1. If it searchs the terminal end first, it will simply get
// added to the itinerary first as it should, and the proper route
// will still be traversed since its entry is still on the stack.
// 2. If it search the proper route first, the dead end route will also
// get added to the itinerary first.
itinerary.push_back(topAirport);
dfs.pop();
}
else {
// Otherwise push the outgoing edge to the dfs stack and
// remove it from the node.
dfs.push(*(graph[topAirport].begin()));
graph[topAirport].erase(graph[topAirport].begin());
}
}
// Reverse the itinerary.
reverse(itinerary.begin(), itinerary.end());
return itinerary;
}
};

https://discuss.leetcode.com/topic/37631/c-non-recursive-o-n-time-o-n-space-solution-with-detail-explanations

C++ non-recursive O(N)-time O(N)-space solution with detail explanations

The idea of this algorithm, which was originally found in fangyang’s thread https://leetcode.com/discuss/84706/share-solution-java-greedy-stack-15ms-with-explanation, consists of two steps:

Step 1: Store the flight in a hash map. (say m in the code below. This map enables us to find all possible destinations from a place in amortized constant time.)

Step 2: Use a greedy and trace-back approach to find the optimal itinerary. Specifically, we use greedy method to find a lexicographically-smallest path until we can not move any further (the path can be stored in a vector, say march in the code below). Each time we reach such an exhaustive state, we find a place which is exactly the end of the itinerary. (The reason is, the path march is an optimal itinerary expect that some loops are omitted. The optimal itinerary can be obtained by inserting some loops into this path, which does not change the last vertex of the path.) Therefore, we can record the last vertex in another place (say results in the code below). So and so forth, the vector results stores the optimal itinerary reversely, since we always place the optimal last vertex at the end of this vector. Reversing the vertex results leads to the correct answer.

Example:
This example is originally shown in StefanPochmann’s thread https://leetcode.com/discuss/84659/short-ruby-python-java-c

[ Source of this picture: http://www.stefan-pochmann.info/misc/reconstruct-itinerary.png ]

In Step 2, we first march greedily, and get the vector march as:

1
march: JFK -> A -> C -> D -> A      (the red path)

However, the optimal itinerary, is

1
JFK -> A -> C -> D( -> B -> C -> JFK -> D) -> A

where the loop (D -> B -> C -> JFK -> D) shall be inserted in the vector march. However, we have already found the last vertex A, Therefore, we can record this result. So march and results become

1
2
march: JFK -> A -> C -> D
results: A

Then we march greedily again, results in

1
2
march: JFK -> A -> C -> D -> B -> C -> JFK -> D
results: A

Now all edges are used. Before the final reversion, march and results become

1
2
march: (empty)
results: A <- D <- JFK <- C <- B <- D <- C <- A <- JFK

Overall Complexities:

Let N be the number of tickets. Let D be the largest outgoing degree of a vertex.

Time: O(N log D)

Step 1: O(N log D)

Step 2: O(N). Each vertex needs to be put into march once and be moved from march to results. At the very end, results is reversed.

Space: O(N)

The map m needs to store all vertices.

Code (40 ms):

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
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {

// Step 1: Store directed edges in a hash map
unordered_map<string, multiset<string>> m;
for (const pair<string, string> & ticket : tickets) {
m[ticket.first].insert(ticket.second);
}

// Step 2: March greedily and traceback
vector<string> march = { "JFK" }; // the storage for greedy searching
vector<string> results; // store the final results reversely
while (march.empty() == false) {
string & from = march.back();
if ((m.find(from) != m.end()) && (m[from].empty() == false)) { // march further
multiset<string> & to = m[from];
march.push_back(*(to.begin()));
to.erase(to.begin());
} else { // can not march further, trace back
results.push_back(march.back()); // archive the last place
march.pop_back();
}
}
reverse(results.begin(), results.end()); // reverse the entries back
return results;
}
};

https://discuss.leetcode.com/topic/46577/28ms-c-beat-100-short-and-elegant

28ms C++ beat 100% Short and Elegant.

I think this algorithm is often called Fleury’s algorithm. But actually it is Hierholzer’s algorithm according to the wiki. Anyway, it works like this:

Keep going one path until stuck, then retreat and push the vertices along the route to a stack until it reaches a vertex that has alternative paths, then go along that path and repeat the process.
The assumption for this to work is there is guaranteed to exist one Euler path. (This problem is basically to find a Euler path of a graph).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
vector<string> result;
void dfs(string vtex)
{
auto & edges = graph[vtex];
while (!edges.empty())
{
string to_vtex = edges.top();
edges.pop();
dfs(to_vtex);
}
result.push_back(vtex);
}
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
for (auto e : tickets)
graph[e.first].push(e.second);
dfs("JFK");
reverse(result.begin(), result.end());
return result;
}
};

https://discuss.leetcode.com/topic/36445/c-solution-using-dfs

C++ Solution using DFS

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
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
vector<string> ans;
int n = tickets.size();
for(int i = 0; i < n; ++ i){
g[tickets[i].first].insert(tickets[i].second);
}
dfs("JFK", ans, 1, n);
// puts(" -- ");
reverse(ans.begin(), ans.end());
return ans;
}
private:
void dfs(string u, vector<string> &ans, int dep, int tot){
while(g[u].size()){
string v = *g[u].begin();
g[u].erase(g[u].begin());
dfs(v, ans, dep + 1, tot);
}
ans.push_back(u);
}
private:
unordered_map<string, multiset<string> > g;
//unordered_map<string, set<string>::iterator> vis;
};

https://discuss.leetcode.com/topic/36403/python-dfs-backtracking

Python Dfs Backtracking

I use a dictionary to represent the tickets (start -> [list of possible destinations]). Then, I start the route at JFK and I dfs from there. Since I do the dfs in sorted order, the first time that I find a possible route, I can return it and know that it is in the smallest lexigraphic order. Finally, note that the worked variable either contains None (as a result of a failed search) or the correct route.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findItinerary(self, tickets):
d = defaultdict(list)
for flight in tickets:
d[flight[0]] += flight[1],
self.route = ["JFK"]
def dfs(start = 'JFK'):
if len(self.route) == len(tickets) + 1:
return self.route
myDsts = sorted(d[start])
for dst in myDsts:
d[start].remove(dst)
self.route += dst,
worked = dfs(dst)
if worked:
return worked
self.route.pop()
d[start] += dst,
return dfs()

108ms, 56.72%, 79/79, April.26th, 2016

https://leetcode.com/discuss/84659/short-ruby-python-java-c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
targets = collections.defaultdict(list)
for a, b in sorted(tickets)[::-1]:
targets[a] += b,
route = []
def visit(airport):
while targets[airport]:
visit(targets[airport].pop())
route.append(airport)
visit('JFK')
return route[::-1]
谢谢你,可爱的朋友。