rustgym 0.2.0

rustgym solutions
Documentation 
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
66
67
68
69
70
71
72
73
74
75
76
77
78

struct Solution;
use std::collections::VecDeque;

impl Solution {
    fn alien_order(words: Vec<String>) -> String {
        let mut alphabet = vec![false; 256];
        for s in words.iter() {
            for b in s.chars() {
                alphabet[b as usize] = true;
            }
        }
        let k: usize = alphabet.iter().map(|&b| if b { 1 } else { 0 }).sum();
        let mut edges: Vec<Vec<u8>> = vec![vec![]; 256];
        for w in words.windows(2) {
            if w[0] == w[1] {
                continue;
            }
            if w[0].starts_with(&w[1]) {
                return "".to_string();
            }
            if let Some((t, h)) = w[0]
                .bytes()
                .zip(w[1].bytes())
                .skip_while(|(t, h)| t == h)
                .take(1)
                .next()
            {
                edges[t as usize].push(h);
            }
        }
        let mut indegree: Vec<usize> = vec![0; 256];
        for i in 0..256 {
            for &h in &edges[i] {
                indegree[h as usize] += 1;
            }
        }
        let mut queue: VecDeque<u8> = VecDeque::new();
        for i in 0..256 {
            if alphabet[i] && indegree[i] == 0 {
                queue.push_back(i as u8);
            }
        }

        let mut res = "".to_string();
        while let Some(t) = queue.pop_front() {
            res.push(t as char);
            let n = edges[t as usize].len();
            for i in 0..n {
                let h = edges[t as usize][i];
                indegree[h as usize] -= 1;
                if indegree[h as usize] == 0 {
                    queue.push_back(h);
                }
            }
        }
        if k == res.len() {
            res
        } else {
            "".to_string()
        }
    }
}

#[test]
fn test() {
    let words = vec_string!["wrt", "wrf", "er", "ett", "rftt"];
    let res = "wertf".to_string();
    assert_eq!(Solution::alien_order(words), res);
    let words = vec_string!["z", "x"];
    let res = "zx".to_string();
    assert_eq!(Solution::alien_order(words), res);
    let words = vec_string!["z", "x", "z"];
    let res = "".to_string();
    assert_eq!(Solution::alien_order(words), res);
    let words = vec_string!["abc", "ab"];
    let res = "".to_string();
    assert_eq!(Solution::alien_order(words), res);
}