Alien dictionary

Array String Depth-First Search Breadth-First Search Graph Theory Topological Sort

37.1% acceptance

Mar 31, 2026

4673

1038

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language. If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "". Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn alien_order(words: Vec<String>) -> String {
    use std::collections::{HashMap, VecDeque};
    let mut in_degree: HashMap<u8, i32> = HashMap::new();
    let mut adj: HashMap<u8, Vec<u8>> = HashMap::new();
    
    // Initialize all characters
    for w in &words {
      for &b in w.as_bytes() {
        in_degree.entry(b).or_insert(0);
        adj.entry(b).or_default();
      }
    }
    
    // Build graph from adjacent word pairs
    for i in 0..words.len() - 1 {
      let w1 = words[i].as_bytes();
      let w2 = words[i + 1].as_bytes();
      // Check if w1 is a prefix of w2 but longer
      if w1.len() > w2.len() && w1.starts_with(w2) {
        return String::new();
      }
      for j in 0..w1.len().min(w2.len()) {
        if w1[j] != w2[j] {
          adj.entry(w1[j]).or_default().push(w2[j]);
          *in_degree.entry(w2[j]).or_insert(0) += 1;
          break;
        }
      }
    }
    
    // Topological sort (BFS)
    let mut queue: VecDeque<u8> = VecDeque::new();
    for (&ch, &deg) in &in_degree {
      if deg == 0 {
        queue.push_back(ch);
      }
    }
    
    let mut result = Vec::new();
    while let Some(ch) = queue.pop_front() {
      result.push(ch);
      if let Some(neighbors) = adj.get(&ch) {
        for &next in neighbors {
          *in_degree.get_mut(&next).unwrap() -= 1;
          if in_degree[&next] == 0 {
            queue.push_back(next);
          }
        }
      }
    }
    
    if result.len() != in_degree.len() {
      return String::new();
    }
    String::from_utf8(result).unwrap()
  }
}