pub fn num_similar_groups(strs: Vec<String>) -> i32 {
    fn is_similar(s1: &str, s2: &str) -> bool {
        s1.chars().zip(s2.chars()).filter(|(a, b)| !a.eq(b)).count() <= 2
    }
    let mut uf = UnionFind::new(strs.len());

    for i in 0..strs.len() {
        let s1 = strs.get(i).unwrap();
        for j in i + 1..strs.len() {
            if uf.is_connected(i, j) {
                continue;
            }

            let s2 = strs.get(j).unwrap();
            if is_similar(s1, s2) {
                uf.connect(i, j);
            }
        }
    }
    uf.count() as i32
}


struct UnionFind {
    count: usize,                           // 连通分量的个数, 总共分成了几组
    parent: std::cell::RefCell<Vec<usize>>, // 记录每个节点的父节点，父节点为自身的是根节点
    size: Vec<usize>,                       // 记录每个连通分量的大小
}

impl UnionFind {
    pub fn new(size: usize) -> Self {
        Self {
            count: size,
            parent: std::cell::RefCell::new((0..size).collect()),
            size: vec![1; size],
        }
    }
    pub fn count(&self) -> usize {
        self.count
    }
    pub fn find(&self, p: usize) -> usize {
        let mut root = p;
        while root != self.parent.borrow()[root] {
            root = self.parent.borrow()[root];
        }
        let mut p = p;
        while p != root {
            let next = self.parent.borrow()[p];
            self.parent.borrow_mut()[p] = root;
            p = next;
        }
        root
    }

    pub fn is_connected(&self, p: usize, q: usize) -> bool {
        self.find(p) == self.find(q)
    }
    pub fn connect(&mut self, p: usize, q: usize) {
        let (p_root, q_root) = (self.find(p), self.find(q));
        if p_root == q_root {
            return;
        }
        if self.size[p_root] < self.size[q_root] {
            self.parent.borrow_mut()[p_root] = q_root;
            self.size[q_root] += self.size[p_root];
        } else {
            self.parent.borrow_mut()[q_root] = p_root;
            self.size[p_root] += self.size[q_root];
        }
        self.count -= 1;
    }
}