2022-05-08：给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。

如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：

往 s1 的字母集合中添加一个字母。 从 s1 的字母集合中删去一个字母。 将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。 数组 words 可以分为一个或者多个无交集的 组 。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。

注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。

请你返回一个长度为 2 的数组 ans ：

ans[0] 是 words 分组后的 总组数 。 ans[1] 是字符串数目最多的组所包含的字符串数目。

输入：words = ["a","b","ab","cde"]。 输出：[2,3]。 解释：

  • words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 关联。
  • words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 关联。
  • words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。
  • words[3] 与 words 中其他字符串都不关联。 所以，words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。

力扣2157. 字符串分组。

答案2022-05-08：

并查集。

代码用rust编写。代码如下：

use std::collections::HashMap;

fn main() {
    let words: Vec<&str> = vec!["a", "b", "ab", "cde"];
    let answer = group_strings2(&words);
    println!("answer = {:?}", answer);
}

fn group_strings2(words: &Vec<&str>) -> Vec<isize> {
    let n = words.len() as isize;
    let mut uf: UnionFind = UnionFind::new(n);
    let mut strs: Vec<isize> = vec![];
    for _i in 0..n {
        strs.push(0);
    }
    let mut stands: HashMap<isize, isize> = HashMap::new();
    for i in 0..n {
        let mut status: isize = 0;
        for c in words[i as usize].chars() {
            status |= 1 << (c as u8 - 'a' as u8);
        }
        strs[i as usize] = status;

        let mut isnone = false;
        match stands.get(&status) {
            Some(value) => uf.union(*value, i),
            None => isnone = true,
        }
        if isnone {
            stands.insert(status, i);
        }
    }
    for i in 0..n {
        let yes = strs[i as usize];
        let no = (!yes) & ((1 << 26) - 1);
        let mut tmp_yes = yes;
        let mut tmp_no = no;
        let mut right_one_yes;
        let mut right_one_no;

        // 0....0 0110011
        //
        // 0....0 0110011
        // 0....0 0000001 -> 用

        // 0....0 0110010
        // 0....0 0000010 -> 用

        // 0....0 0110000

        while tmp_yes != 0 {
            right_one_yes = tmp_yes & (-tmp_yes);
            let isok: bool;
            match stands.get(&(yes ^ right_one_yes)) {
                Some(_value) => isok = true,
                None => isok = false,
            }
            if isok {
                uf.union(i, *stands.get(&(yes ^ right_one_yes)).unwrap());
            }
            tmp_yes ^= right_one_yes;
        }

        // tmpNo = 该去试试什么添加！
        while tmp_no != 0 {
            right_one_no = tmp_no & (-tmp_no);
            let isok: bool;
            match stands.get(&(yes | right_one_no)) {
                Some(_value) => isok = true,
                None => isok = false,
            }
            if isok {
                uf.union(i, *stands.get(&(yes | right_one_no)).unwrap());
            }
            tmp_no ^= right_one_no;
        }
        tmp_yes = yes;
        while tmp_yes != 0 {
            right_one_yes = tmp_yes & (-tmp_yes);
            tmp_no = no;
            while tmp_no != 0 {
                right_one_no = tmp_no & (-tmp_no);
                let isok: bool;
                match stands.get(&((yes ^ right_one_yes) | right_one_no)) {
                    Some(_value) => isok = true,
                    None => isok = false,
                }
                if isok {
                    uf.union(
                        i,
                        *stands.get(&((yes ^ right_one_yes) | right_one_no)).unwrap(),
                    );
                }
                tmp_no ^= right_one_no;
            }
            tmp_yes ^= right_one_yes;
        }
    }
    let ans: Vec<isize> = vec![uf.sets(), uf.max_size()];
    return ans;
}

pub struct UnionFind {
    pub parent: Vec<isize>,
    pub size: Vec<isize>,
    pub help: Vec<isize>,
}

impl UnionFind {
    pub fn new(n: isize) -> UnionFind {
        let mut parent: Vec<isize> = vec![];
        let mut size: Vec<isize> = vec![];
        let mut help: Vec<isize> = vec![];
        for i in 0..n {
            parent.push(i);
            size.push(1);
            help.push(0);
        }

        UnionFind {
            parent: parent,
            size: size,
            help: help,
        }
    }

    pub fn find(&mut self, i: isize) -> isize {
        let mut i = i;
        let mut hi: isize = 0;
        while i != self.parent[i as usize] {
            self.help[hi as usize] = i;
            hi += 1;
            i = self.parent[i as usize];
        }
        hi -= 1;
        while hi >= 0 {
            self.parent[self.help[hi as usize] as usize] = i;
            hi -= 1;
        }
        return i;
    }

    pub fn union(&mut self, i: isize, j: isize) {
        let f1 = self.find(i);
        let f2 = self.find(j);
        if f1 != f2 {
            if self.size[f1 as usize] >= self.size[f2 as usize] {
                self.size[f1 as usize] += self.size[f2 as usize];
                self.parent[f2 as usize] = f1;
            } else {
                self.size[f2 as usize] += self.size[f1 as usize];
                self.parent[f1 as usize] = f2;
            }
        }
    }

    pub fn sets(&mut self) -> isize {
        let mut ans: isize = 0;
        for i in 0..self.parent.len() {
            ans += if self.parent[i] == i as isize { 1 } else { 0 };
        }
        return ans;
    }

    pub fn max_size(&mut self) -> isize {
        let mut ans: isize = 0;
        for i in 0..self.size.len() {
            ans = if ans > self.size[i as usize] {
                ans
            } else {
                self.size[i as usize]
            };
        }
        return ans;
    }
}

执行结果如下：

在这里插入图片描述

左神java代码