一、题目
1、题目描述
给你一个下标从
00
0
开始的字符串数组
wo
r
d
s
words
w
o
r
d
s
。每个字符串都只包含小写英文字母 。
wo
r
d
s
words
w
o
r
d
s
中任意一个子串中，每个字母都至多只出现一次。如果通过以下操作之一，我们可以从
s1
s1
s
1
的字母集合得到
s2
s2
s
2
的字母集合，那么我们称这两个字符串为 关联的 ：
1、往 s1 的字母集合中添加一个字母。
2、从 s1 的字母集合中删去一个字母。
3、将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。
数组
wo
r
d
s
words
w
o
r
d
s
可以分为一个或者多个无交集的组 。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。请你返回一个长度为 2 的数组 ans ：
ans[0] 是 words 分组后的 总组数 。
ans[1] 是字符串数目最多的组所包含的字符串数目。
样例输入：
["a","b","ab","cde"]
样例输出：
[2,3]
2、基础框架
- C语言 版本给出的基础框架代码如下：
int* groupStrings(char ** words, int wordsSize, int* returnSize){
}
3、原题链接
二、解题报告
1、思路分析
(
1
)
(1)
(
1
)
容易得知，一旦产生关联，一定是双向关联。比如
a
a
a
可以删除一个字符后，变成
b
b
b
；那么
b
b
b
就可以通过 添加一个字符变成
a
a
a
。同样的，替换也是满足这个定律的。所以只要
a
a
a
关联
b
b
b
，
b
b
b
就一定关联
a
a
a
。说明这是一个图的双向边。
(
2
)
(2)
(
2
)
由于每个字符串的字母都是唯一的，所以我们可以用 0 和 1 来表示这个字符串中对应字母中在不在，用一个 26 位的二进制数表示每个字符串，由于数字较大，所以需要用哈希映射到较小的范围区间内。
(
3
)
(3)
(
3
)
首先对于每个字符串，我们先把它变成一个掩码
mask
，可以通过左移和位或来实现。如下代码表示，对于第
i
i
i
个字符，生成它的掩码。
mask = 0;
for(j = 0; j < words[i].size(); ++j) {
mask |= (1 << (words[i][j] - 'a'));
}
(
4
)
(4)
(
4
)
用一个哈希表
id
标记
mask
对应的唯一标识。并且用
cnt[ID]
数组来记录对应的结点的数目。
id2Mask
则代表的是
id
这个哈希表的反向映射。
更加详细的，
id
是键为
mask
值为
ID
的哈希表，
id2Mask
是值为
mask
键为
ID
哈希表。两者互为反射。
unordered_map< int, int > id;
if(id.find( mask ) == id.end()) {
id[ mask ] = ++ID;
cnt[ ID ] = 1;
id2Mask[ ID ] = mask;
}else {
cnt[ id[ mask ] ]++;
}
(
5
)
(5)
(
5
)
对于每一个
mask
对应的
ID
进行搜索找连通块并且染色。
(
6
)
(6)
(
6
)
染色的过程，扩展结点可以用深度优先搜索加二进制枚举，对于结点的扩展，只有三种情况。
(
6.1
)
(6.1)
(
6
.
1
)
二进制位上去掉一个一；
(
6.2
)
(6.2)
(
6
.
2
)
二进制位上加上一个一；
(
6.3
)
(6.3)
(
6
.
3
)
二进制位上加上一个一，再去掉一个一；
(
7
)
(7)
(
7
)
最后将染色完的结点进行分组统计即可。
2、时间复杂度
O
(
n
∗
26
∗
26
)
O(n*26*26)
O
(
n
∗
2
6
∗
2
6
)
。
3、代码详解
#define maxn 20010
class Solution {
int color[maxn], colorCnt;
unordered_map< int, int > id;
int id2Mask[maxn];
int cnt[maxn];
void dfs(int u, int c) {
int x = id2Mask[u];
int i, j;
if(color[u] != -1) {
return ;
}
color[u] = c;
// 对于 id2Mask[u] 来说，只有三种情况：
// 1. 二进制位上去掉一个1
for(i = 0; i < 26; ++i) {
if(x & (1<<i)) {
int v = (x ^ (1<<i));
if( id.find(v) != id.end() ) {
dfs( id[v], c );
}
}
}
// 2. 二进制位上加上一个1
for(i = 0; i < 26; ++i) {
if(x & (1<<i)) {
continue;
}else {
int v = (x ^ (1<<i));
if( id.find(v) != id.end() ) {
dfs( id[v], c );
}
}
}
// 3. 二进制位上去掉1个1，再在另一个位置上加上1个1
for(i = 0; i < 26; ++i) {
if( !(x & (1<<i)) ) {
continue;
}
for(j = 0; j < 26; ++j) {
if(i == j) {
continue;
}else if( !(x & (1<<j)) ) {
int v = (x ^ (1<<i) ^ (1<<j));
if( id.find(v) != id.end() ) {
dfs( id[v], c );
}
}
}
}
}
public:
vector<int> groupStrings(vector<string>& words) {
int i, j;
int mask;
int ID = 0;
int maxColor = -1;
int hashColor[maxn];
id.clear();
memset(color, -1, sizeof(color));
for(i = 0; i < words.size(); ++i) {
mask = 0;
for(j = 0; j < words[i].size(); ++j) {
mask |= (1 << (words[i][j] - 'a'));
}
if(id.find( mask ) == id.end()) {
id[ mask ] = ++ID;
cnt[ ID ] = 1;
id2Mask[ ID ] = mask;
}else {
cnt[ id[ mask ] ]++;
}
}
colorCnt = 0;
// 1 -> ID
for(i = 1; i <= ID; ++i) {
if(-1 == color[i]) {
dfs(i, colorCnt);
++colorCnt;
}
}
memset(hashColor, 0, sizeof(hashColor));
for(i = 1; i <= ID; ++i) {
hashColor[ color[i] ] += cnt[i];
}
for(i = 0; i < colorCnt; ++i) {
if(hashColor[i] > maxColor) {
maxColor = hashColor[i];
}
}
return {colorCnt, maxColor};
}
};
三、本题小知识
本题的切入点在于字母是集合，不是序列，所以可以采用二进制压缩。
四、加群须知
相信看我文章的大多数都是
「 大学生 」
，能上大学的都是
「 精英 」
，那么我们自然要
「 精益求精 」
，如果你还是
「 大一 」
，那么太好了，你拥有大把时间，当然你可以选择
「 刷剧 」
，然而，
「 学好算法 」
，三年后的你自然
「 不能同日而语 」
。
那么这里，我整理了
「 几十个基础算法 」
的分类，点击开启：
🌌《
算法入门指引
》🌌
如果链接被屏蔽，或者有权限问题，可以私聊作者解决。
大致题集一览：
为了让这件事情变得有趣，以及
「 照顾初学者 」
，目前题目只开放最简单的算法
「 枚举系列 」
（包括：
线性枚举、双指针、前缀和、二分枚举、三分枚举
），当有 一半成员刷完
「 枚举系列 」
的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为
「 夜深人静写算法 」专家团
的一员。
不要小看这个专家团，三年之后，你将会是别人
望尘莫及
的存在。如果要加入，可以联系我，考虑到大家都是学生，
没有「 主要经济来源 」
，在你成为神的路上，
「 不会索取任何 」
。
🔥联系作者，或者扫作者主页二维码加群，加入刷题行列吧🔥
🔥让天下没有难学的算法🔥
C语言免费动漫教程，和我一起打卡！
🌞《
光天化日学C语言
》🌞
让你养成九天持续刷题的习惯
🔥《
九日集训
》🔥
入门级C语言真题汇总
🧡《
C语言入门100例
》🧡
组团学习，抱团生长
🌌《
算法零基础100讲
》🌌
几张动图学会一种数据结构
🌳《
画解数据结构
》🌳
竞赛选手金典图文教程
💜《
夜深人静写算法
》💜