Reconstruct Itinerary
HardThe problem
Each ticket is a pair [from, to] of airport names. Using every ticket exactly once, build a trip that starts at "JFK". Return the list of airports in the order you visit them. If more than one trip works, return the one that comes first when compared alphabetically airport by airport.
- Example 1Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Only one trip uses all four tickets.
- Example 2Input: tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]Output: ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
Another valid trip is JFK, SFO, ATL, JFK, ATL, SFO, but "ATL" sorts before "SFO", so the first one wins.
- 1 ≤ len(tickets) ≤ 300
- Airport names are 3 uppercase letters
- At least one trip that uses every ticket exists
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
You must use every ticket exactly once, and pick the smallest airport first. Which kind of path is that?
The idea
Hierholzer's algorithm: sort destinations, DFS taking the smallest unused edge, append the airport after its edges are exhausted, then reverse the result.
Target: O(E log E) time
Go function shape
func findItinerary(tickets [][]string) []stringReference solution
Tested with go test. Try it yourself first, then compare.
// FindItinerary: use every ticket once, smallest airport name first (Hierholzer's algorithm).
func FindItinerary(tickets [][]string) []string {
adj := map[string][]string{}
for _, t := range tickets {
adj[t[0]] = append(adj[t[0]], t[1])
}
for from := range adj {
sort.Sort(sort.Reverse(sort.StringSlice(adj[from]))) // reversed so popping the end gives the smallest
}
var route []string
var visit func(string)
visit = func(airport string) {
for len(adj[airport]) > 0 {
next := adj[airport][len(adj[airport])-1]
adj[airport] = adj[airport][:len(adj[airport])-1]
visit(next)
}
route = append(route, airport) // added only once stuck: dead ends end up at the back
}
visit("JFK")
for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
route[i], route[j] = route[j], route[i]
}
return route
}