- 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:

- 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”].
- All airports are represented by three capital letters (IATA code).
- You may assume all tickets form at least one valid itinerary.

1 | Example 1: |

1 | Example 2: |

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 | def findItinerary(self, tickets): |

Java

1 | public List<String> findItinerary(String[][] tickets) { |

C++

1 | vector<string> findItinerary(vector<pair<string, string>> tickets) { |

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.

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

1 | class Solution { |

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 | march: JFK -> A -> C -> D |

Then we march greedily again, results in

1 | march: JFK -> A -> C -> D -> B -> C -> JFK -> D |

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

1 | march: (empty) |

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 | class Solution { |

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 | class Solution { |

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

C++ Solution using DFS

1 | class Solution { |

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 | def findItinerary(self, tickets): |

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

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

1 | class Solution(object): |