[数据结构与算法]力扣2157——字符串分组（状态压缩+BFS）

题目链接

字符串分组

解题思路

每个字母最多出现一次，且字母集合与顺序无关，也就是统计出现次数；

一个int的前26位代表该位字母是否出现，来存一种字母集合，通过位运算<<进行状态压缩；

对于每种字母集合对应的数字，他的关联字母集合代表的数字可以通过位运算异或出来；（每位异或表示增减，分别01的两位同时取反就是交换）

如果存在关联，就相当于存在一条无向边；

答案是求连通块数和最大连通块大小；

用BFS求解，并记录已访问节点；

对应每种关联的结果，先判断是否存在会快一些；

代码

class Solution {
public:
    vector<int> islink(int num) {
        vector<int> ans;
        for(int i = 0; i < 26; i++) {   //添加或删去
            ans.push_back(num ^ (1 << i));
        }
        for(int i = 0; i < 26; i++) {   //替换
            if(num & (1 << i)) {
                for(int j = 0; j < 26; j++) {
                    if(!(num & (1 << j))) 
                        ans.push_back(num ^ (1 << i) ^ (1 << j));
                }
            }
        }
        return ans;
    }
    vector<int> groupStrings(vector<string>& words) {
        int n = words.size();
        unordered_map<int, int> hash;   //状态压缩的单词和次数
        for(auto s : words) {
            int num = 0;
            for(int i = 0; i < s.size(); i++) {
                num |= 1 << s[i] - 'a';
            }
            hash[num]++;
        }
        
        unordered_set<int> vis;
        int Group = 0, MaxGroupSize = 0;
        for(auto [num, cnt] : hash) {
            if(vis.count(num)) continue;
            Group++;
            int tmpsize = cnt;
            queue<int> q;
            q.push(num);
            vis.insert(num);
            while(!q.empty()) {
                int tmp = q.front(); q.pop();
                for(auto next : islink(tmp)) {
                    if(hash.count(next) && !vis.count(next)) {
                        tmpsize += hash[next];
                        vis.insert(next);
                        q.push(next);
                    }
                }
            }
            MaxGroupSize = max(MaxGroupSize, tmpsize);
        }
        return {Group, MaxGroupSize};        
    }
};