Synonymous sentences

Array Hash Table String Backtracking Sort Union-Find

57.2% acceptance

Mar 31, 2026

373

171

No description available.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn generate_sentences(synonyms: Vec<Vec<String>>, text: String) -> Vec<String> {
    // Union-Find to group synonyms
    let mut parent: HashMap<String, String> = HashMap::new();

    fn find(parent: &mut HashMap<String, String>, x: &str) -> String {
      if !parent.contains_key(x) {
        parent.insert(x.to_string(), x.to_string());
        return x.to_string();
      }
      if parent[x] == x {
        return x.to_string();
      }
      let p = parent[x].clone();
      let root = find(parent, &p);
      parent.insert(x.to_string(), root.clone());
      root
    }

    fn union(parent: &mut HashMap<String, String>, a: &str, b: &str) {
      let ra = find(parent, a);
      let rb = find(parent, b);
      if ra < rb {
        parent.insert(rb, ra);
      } else {
        parent.insert(ra, rb);
      }
    }

    for syn in &synonyms {
      union(&mut parent, &syn[0], &syn[1]);
    }

    // Group all words by their root
    let mut groups: HashMap<String, Vec<String>> = HashMap::new();
    let keys: Vec<String> = parent.keys().cloned().collect();
    for k in keys {
      let root = find(&mut parent, &k);
      groups.entry(root).or_default().push(k);
    }
    for v in groups.values_mut() {
      v.sort();
    }

    let words: Vec<&str> = text.split_whitespace().collect();
    let mut results: Vec<String> = vec![String::new()];

    for word in &words {
      let root = find(&mut parent, word);
      let default = vec![word.to_string()];
      let options = groups.get(&root).unwrap_or(&default);
      let mut new_results = Vec::new();
      for existing in &results {
        for opt in options {
          let mut s = existing.clone();
          if !s.is_empty() { s.push(' '); }
          s.push_str(opt);
          new_results.push(s);
        }
      }
      results = new_results;
    }

    results.sort();
    results
  }
}