rustgym/leetcode/
_332_reconstruct_itinerary.rs

1struct Solution;
2use std::cmp::Reverse;
3use std::collections::BinaryHeap;
4use std::collections::HashMap;
5
6type G = HashMap<String, BinaryHeap<Reverse<String>>>;
7
8impl Solution {
9    fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
10        let mut res: Vec<String> = vec![];
11        let mut g: G = HashMap::new();
12        for ticket in tickets {
13            g.entry(ticket[0].clone())
14                .or_default()
15                .push(Reverse(ticket[1].clone()));
16        }
17        let mut stack: Vec<String> = vec![];
18        stack.push("JFK".to_string());
19        while !stack.is_empty() {
20            while g.contains_key(stack.last().unwrap())
21                && !g.get(stack.last().unwrap()).unwrap().is_empty()
22            {
23                let airports = g.get_mut(stack.last().unwrap()).unwrap();
24                let airport = airports.pop().unwrap().0;
25                stack.push(airport);
26            }
27            res.insert(0, stack.pop().unwrap());
28        }
29        res
30    }
31}
32
33#[test]
34fn test() {
35    let tickets: Vec<Vec<String>> = vec_vec_string![
36        ["MUC", "LHR"],
37        ["JFK", "MUC"],
38        ["SFO", "SJC"],
39        ["LHR", "SFO"]
40    ];
41    let res: Vec<String> = vec_string!["JFK", "MUC", "LHR", "SFO", "SJC"];
42    assert_eq!(Solution::find_itinerary(tickets), res);
43}
rustgym/leetcode/_332_reconstruct_itinerary.rs

rustgym/leetcode/
_332_reconstruct_itinerary.rs
