Sentence similarity ii

Array Hash Table String Depth-First Search Breadth-First Search Union-Find

51.2% acceptance

Mar 31, 2026

854

We can represent a sentence as an array of words, for example, the sentence "I am happy with leetcode" can be represented as arr = ["I","am",happy","with","leetcode"]. Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar. Return true if sentence1 and sentence2 are similar, or false if they are not similar. Two sentences are similar if: They have the same length (i.e., the same number of words) sentence1[i] and sentence2[i] are similar. Notice that a word is always similar to itself, also notice that the similarity relation is transitive. For example, if the words a and b are similar, and the words b and c are similar, then a and c are similar.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn are_sentences_similar_two(sentence1: Vec<String>, sentence2: Vec<String>, similar_pairs: Vec<Vec<String>>) -> bool {
    if sentence1.len() != sentence2.len() { return false; }
    use std::collections::HashMap;
    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 {
        let p = find(parent, &parent[x].clone());
        parent.insert(x.to_string(), p);
      }
      parent[x].clone()
    }
    
    fn union(parent: &mut HashMap<String, String>, a: &str, b: &str) {
      let pa = find(parent, a);
      let pb = find(parent, b);
      if pa != pb {
        parent.insert(pa, pb);
      }
    }
    
    for pair in &similar_pairs {
      union(&mut parent, &pair[0], &pair[1]);
    }
    
    sentence1.iter().zip(sentence2.iter()).all(|(a, b)| {
      a == b || find(&mut parent, a) == find(&mut parent, b)
    })
  }
}