文章目录- 1. 题目
- 2. 解题
1. 题目
给你一个下标从 0 开始的字符串数组 words 。 每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。
如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：
- 往 s1 的字母集合中添加一个字母。
- 从 s1 的字母集合中删去一个字母。
- 将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。
数组 words 可以分为一个或者多个无交集的 组 。 一个字符串与一个组如果满足以下 任一 条件，它就属于这个组：
- 它与组内 至少 一个其他字符串关联。
- 它是这个组中 唯一 的字符串。
注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。
请你返回一个长度为 2 的数组 ans ：
- ans[0] 是 words 分组后的 总组数 。
- ans[1] 是字符串数目最多的组所包含的字符串数目。
示例 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 。
示例 2：
输入：words = ["a","ab","abc"]
输出：[1,3]
解释：
- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。
所以最大的组大小为 3 。
提示：
1 <= words.length <= 2 * 10^4
1 <= words[i].length <= 26
words[i] 只包含小写英文字母。
words[i] 中每个字母最多只出现一次。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/groups-of-strings 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 把单词26个字符是否出现作为 int 数的一个 bit 的 01 ，把字符串转成数字，并记录个数（有重复的字符串）
- 枚举 每个数字的 26 个位，使用题目给的3中规则进行变形，得到其他的数字，如果数字出现过，则这两个数字节点有一条无向边，构建图
- 图的遍历，找到连通块的数量，最大连通块的节点个数
class Solution {
public:
vector<int> groupStrings(vector<string>& words) {
unordered_map<int, unordered_set<int>> g;
unordered_set<int> node;
unordered_map<int, int> node_ct;
for(auto& w : words)
{
int num = 0;
for(auto c : w)
num |= 1<<(c-'a'); // 单词转26bit 数字
node.insert(num);
node_ct[num] ; // 有重复的，需要计数
}
for(auto num : node)
{
for(int i = 0; i < 26; i)
{ // 遍历所有的 bit
if((num>>i)&1) // i 位是 1
{
int othernum = num & ~(1<<i); // 删除i位
if(node.find(othernum) != node.end())
{
g[num].insert(othernum);
g[othernum].insert(num);
}
for(int j = 0; j < 26; j)
{ // 先删除一个1，再添加一个1，替换字母
if(i==j || ((othernum>>j)&1)==1) continue;
int anothernum = othernum | (1<<j);
if(node.find(anothernum) != node.end())
{
g[num].insert(anothernum);
g[anothernum].insert(num);
}
}
}
else // i 位是 0，可以添加一位1
{
int othernum = num | (1<<i); // 添加i位
if(node.find(othernum) != node.end())
{
g[num].insert(othernum);
g[othernum].insert(num);
}
}
}
}
// 遍历图，找连通块的数量和最大的块的节点数量
unordered_set<int> vis; // 访问过的点的集合
int group = 0, ct = 0, maxct = 0;
for(auto num : node)
{
if(vis.find(num) != vis.end()) continue;
group ;
queue<int> q;
q.push(num);
vis.insert(num);
ct = 0;
while(!q.empty())
{
int tp = q.front();
ct = node_ct[tp];
q.pop();
for(auto nt : g[tp])
{
if(vis.find(nt) != vis.end()) continue;
q.push(nt);
vis.insert(nt);
}
}
maxct = max(maxct, ct);
}
return {group, maxct};
}
};1276 ms 199.5 MB C
我的CSDN博客地址 https://michael.blog.csdn.net/
