-
Notifications
You must be signed in to change notification settings - Fork 2
/
0332-reconstruct-itinerary.rs
65 lines (58 loc) · 1.84 KB
/
0332-reconstruct-itinerary.rs
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct Solution;
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
impl Solution {
pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
let mut itinerary = Vec::new();
if tickets.is_empty() {
return itinerary;
}
// source => destinations (as a min-heap)
let mut flights: HashMap<&str, BinaryHeap<Reverse<&str>>> = HashMap::new();
for ticket in &tickets {
let (src, dst) = (&ticket[0], &ticket[1]);
let flights_from_src = flights.entry(&src).or_default();
flights_from_src.push(Reverse(&dst));
}
let mut stack = Vec::new();
stack.push("JFK");
while !stack.is_empty() {
let src = stack.last().unwrap();
if let Some(destinations) = flights.get_mut(src) {
if let Some(Reverse(dst)) = destinations.pop() {
stack.push(dst);
continue;
}
}
itinerary.push(src.to_string());
stack.pop();
}
itinerary.reverse();
itinerary
}
}
fn to_tickets(tickets: Vec<[&str; 2]>) -> Vec<Vec<String>> {
tickets
.into_iter()
.map(|s| s.iter().map(|l| l.to_string()).collect())
.collect()
}
fn main() {
let tickets = to_tickets(vec![
["MUC", "LHR"],
["JFK", "MUC"],
["SFO", "SJC"],
["LHR", "SFO"],
]);
let itinerary = vec!["JFK", "MUC", "LHR", "SFO", "SJC"];
assert_eq!(itinerary, Solution::find_itinerary(tickets));
let tickets = to_tickets(vec![
["JFK", "SFO"],
["JFK", "ATL"],
["SFO", "ATL"],
["ATL", "JFK"],
["ATL", "SFO"],
]);
let itinerary = vec!["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"];
assert_eq!(itinerary, Solution::find_itinerary(tickets));
}