269. Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order among letters are unknown to you.

You are given a list of strings `words` from the dictionary, where `words` are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language, and return it. If the given input is invalid, return `""`. If there are multiple valid solutions, return any of them.

Example 1:

```Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
```

Example 2:

```Input: words = ["z","x"]
Output: "zx"
```

Example 3:

```Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return `""`.
```

Constraints:

• `1 <= words.length <= 100`
• `1 <= words[i].length <= 100`
• `words[i]` consists of only lowercase English letters.

269. Alien Dictionary
``````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 == w {
continue;
}
if w.starts_with(&w) {
return "".to_string();
}
if let Some((t, h)) = w
.bytes()
.zip(w.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);
}
``````