Welcome to Subscribe On Youtube
332. Reconstruct Itinerary
Description
You are given a list of airline tickets
where tickets[i] = [fromi, toi]
represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK"
, thus, the itinerary must begin with "JFK"
. 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"]
.
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]
Example 2:
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Constraints:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi
andtoi
consist of uppercase English letters.fromi != toi
Solutions
-
class Solution { void dfs(Map<String, Queue<String>> adjLists, List<String> ans, String curr) { Queue<String> neighbors = adjLists.get(curr); if (neighbors == null) { ans.add(curr); return; } while (!neighbors.isEmpty()) { String neighbor = neighbors.poll(); dfs(adjLists, ans, neighbor); } ans.add(curr); return; } public List<String> findItinerary(List<List<String>> tickets) { Map<String, Queue<String>> adjLists = new HashMap<>(); for (List<String> ticket : tickets) { String from = ticket.get(0); String to = ticket.get(1); if (!adjLists.containsKey(from)) { adjLists.put(from, new PriorityQueue<>()); } adjLists.get(from).add(to); } List<String> ans = new ArrayList<>(); dfs(adjLists, ans, "JFK"); Collections.reverse(ans); return ans; } }
-
class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { unordered_map<string, priority_queue<string, vector<string>, greater<string>>> g; vector<string> ret; // Initialize the graph for (const auto& t : tickets) { g[t[0]].push(t[1]); } findItineraryInner(g, ret, "JFK"); ret = {ret.rbegin(), ret.rend()}; return ret; } void findItineraryInner(unordered_map<string, priority_queue<string, vector<string>, greater<string>>>& g, vector<string>& ret, string cur) { if (g.count(cur) == 0) { // This is the end point ret.push_back(cur); return; } else { while (!g[cur].empty()) { auto front = g[cur].top(); g[cur].pop(); findItineraryInner(g, ret, front); } ret.push_back(cur); } } };
-
class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: graph = defaultdict(list) for src, dst in sorted(tickets, reverse=True): graph[src].append(dst) itinerary = [] def dfs(airport): while graph[airport]: dfs(graph[airport].pop()) itinerary.append(airport) dfs("JFK") return itinerary[::-1]