daoware

Alien dictionary

Nov 28th, 2021
729
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::collections::{HashMap, VecDeque};
  2.  
  3. struct Solution;
  4.  
  5. struct Graph {
  6.     edges: HashMap<char, Vec<char>>,
  7.     indegree: HashMap<char, usize>,
  8. }
  9.  
  10.  
  11. impl Graph {
  12.     fn new() -> Self {
  13.         Graph { edges: HashMap::default(), indegree: HashMap::default() }
  14.     }
  15.  
  16.     fn add_vertex(&mut self, vertex: char) {
  17.         self.edges.entry(vertex).or_insert(vec![]);
  18.         self.indegree.entry(vertex).or_insert(0);
  19.     }
  20.  
  21.     fn add_edge(&mut self, from: char, to: char) {
  22.         self.edges.entry(from).or_insert(vec![]).push(to);
  23.         *self.indegree.entry(to).or_insert(0) += 1;
  24.     }
  25.  
  26.     fn find_dangling(&self) -> Vec<char> {
  27.         self.indegree.iter()
  28.             .filter(|(_, &count)| count == 0)
  29.             .map(|(&vertex, _)| vertex)
  30.             .collect::<Vec<char>>()
  31.     }
  32.  
  33.     fn get_adjacent(&self, vertex: char) -> &Vec<char> {
  34.         self.edges.get(&vertex).unwrap()
  35.     }
  36.  
  37.     fn decrease_incoming(&mut self, vertex: &char) -> Option<usize> {
  38.         match self.indegree.get_mut(vertex) {
  39.             None => None,
  40.             Some(count) => {
  41.                 *count = count.saturating_sub(1);
  42.                 Some(*count)
  43.             }
  44.         }
  45.     }
  46.  
  47.     fn len(&self) -> usize {
  48.         self.edges.len()
  49.     }
  50. }
  51.  
  52. impl Solution {
  53.     pub fn alien_order(words: Vec<String>) -> String {
  54.         let mut result = String::new();
  55.  
  56.         let mut graph = match Self::build_graph(&words) {
  57.             None => return result,
  58.             Some(graph) => graph
  59.         };
  60.  
  61.         let mut queue = VecDeque::from(graph.find_dangling());
  62.  
  63.         while let Some(vertex) = queue.pop_front() {
  64.             result.push(vertex);
  65.  
  66.             for adjacent in graph.get_adjacent(vertex).clone() {
  67.                 match graph.decrease_incoming(&adjacent) {
  68.                     Some(count) if count == 0 => queue.push_back(adjacent),
  69.                     _ => {}
  70.                 }
  71.             }
  72.         }
  73.  
  74.         if result.len() < graph.len() {
  75.             return "".to_string();
  76.         }
  77.  
  78.         result
  79.     }
  80.  
  81.     fn build_graph(words: &[String]) -> Option<Graph> {
  82.         let mut graph = Graph::new();
  83.         words.iter()
  84.             .flat_map(|work| work.chars())
  85.             .for_each(|char| graph.add_vertex(char));
  86.  
  87.         let pair_iter = words.iter().zip(words.iter().skip(1));
  88.         for (w_curr, w_next) in pair_iter {
  89.             // broken ordering
  90.             if w_curr.len() > w_next.len() && w_curr.starts_with(w_next) {
  91.                 return None;
  92.             }
  93.  
  94.             let first_difference = w_curr.chars()
  95.                 .zip(w_next.chars())
  96.                 .find(|(ch_curr, ch_next)| ch_curr != ch_next);
  97.  
  98.             if let Some((ch_curr, ch_next)) = first_difference {
  99.                 graph.add_edge(ch_curr, ch_next);
  100.             }
  101.         }
  102.  
  103.         Some(graph)
  104.     }
  105. }
  106.  
  107.  
  108. #[cfg(test)]
  109. mod tests {
  110.     use arrays::create::LeetCodeArrayTestHelper;
  111.  
  112.     use crate::alien_dictionary::bfs::Solution;
  113.  
  114.     #[test]
  115.     fn test() {
  116.         println!("{:?}", Solution::alien_order(
  117.             ["wrt", "wrf", "er", "ett", "rftt"].to_string_vec()
  118.         ));
  119.     }
  120. }
  121.  
RAW Paste Data