LeetCode Solutions
332. Reconstruct Itinerary
Time: $O(|E|\log |E|)$ Space: $O(|E|)$
class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
vector<string> ans;
unordered_map<string, multiset<string>> graph;
for (const vector<string>& ticket : tickets)
graph[ticket[0]].insert(ticket[1]);
dfs(graph, "JFK", ans);
reverse(begin(ans), end(ans));
return ans;
}
private:
void dfs(unordered_map<string, multiset<string>>& graph, const string& u,
vector<string>& ans) {
while (graph.count(u) && !graph[u].empty()) {
const string v = *begin(graph[u]);
graph[u].erase(begin(graph[u]));
dfs(graph, v, ans);
}
ans.push_back(u);
}
};
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
LinkedList<String> ans = new LinkedList<>();
Map<String, Queue<String>> graph = new HashMap<>();
for (final List<String> ticket : tickets) {
graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
graph.get(ticket.get(0)).offer(ticket.get(1));
}
dfs(graph, "JFK", ans);
return ans;
}
private void dfs(Map<String, Queue<String>> graph, final String u, LinkedList<String> ans) {
final Queue<String> arrivals = graph.get(u);
while (arrivals != null && !arrivals.isEmpty())
dfs(graph, arrivals.poll(), ans);
ans.addFirst(u);
}
}
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
ans = []
graph = defaultdict(list)
for a, b in reversed(sorted(tickets)):
graph[a].append(b)
def dfs(u: str) -> None:
while u in graph and graph[u]:
dfs(graph[u].pop())
ans.append(u)
dfs('JFK')
return ans[::-1]