class Solution {
public:
vector<int> groupStrings(vector<string>& words) {
}
};
2157. 字符串分组
给你一个下标从 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 * 1041 <= words[i].length <= 26words[i] 只包含小写英文字母。words[i] 中每个字母最多只出现一次。原站题解
golang 解法, 执行用时: 528 ms, 内存消耗: 7.9 MB, 提交时间: 2023-09-04 23:40:10
func groupStrings(words []string) (ans []int) {
// 并查集模板（哈希表写法）
fa := map[int]int{}
size := map[int]int{}
var find func(int) int
find = func(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
groups, maxSize := len(words), 0
merge := func(x, y int) {
if _, ok := fa[y]; !ok {
return
}
x, y = find(x), find(y)
if x == y {
return
}
fa[x] = y
size[y] += size[x]
maxSize = max(maxSize, size[y]) // 维护答案
groups--
}
for _, word := range words {
x := 0
for _, ch := range word {
x |= 1 << (ch - 'a') // 计算 word 的二进制表示
}
fa[x] = x // 添加至并查集
size[x]++
maxSize = max(maxSize, size[x]) // 维护答案
if size[x] > 1 {
groups--
}
}
for x := range fa { // 枚举所有字符串（二进制表示）
for i := 0; i < 26; i++ {
merge(x, x^1<<i) // 添加或删除字符 i
if x>>i&1 == 1 {
for j := 0; j < 26; j++ {
if x>>j&1 == 0 {
merge(x, x^1<<i|1<<j) // 替换字符 i 为 j
}
}
}
}
}
return []int{groups, maxSize}
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 1228 ms, 内存消耗: 67.2 MB, 提交时间: 2023-09-04 23:39:26
class Solution {
// 并查集模板（哈希表写法）
unordered_map<int, int> fa, size;
int groups, maxSize = 0;
int find(int x) {
return fa[x] != x ? fa[x] = find(fa[x]) : x;
}
void merge(int x, int y) {
if (!fa.count(y)) return;
x = find(x);
y = find(y);
if (x == y) return;
fa[x] = y;
size[y] += size[x];
maxSize = max(maxSize, size[y]); // 维护答案
--groups;
}
public:
vector<int> groupStrings(vector<string> &words) {
groups = words.size();
for (auto &word : words) {
int x = 0;
for (char ch : word)
x |= 1 << (ch - 'a'); // 计算 word 的二进制表示
fa[x] = x; // 添加至并查集
++size[x];
maxSize = max(maxSize, size[x]); // 维护答案
if (size[x] > 1) --groups;
}
for (auto &[x, _] : fa) { // 枚举所有字符串（二进制表示）
for (int i = 0; i < 26; ++i) {
merge(x, x ^ (1 << i)); // 添加或删除字符 i
if ((x >> i) & 1)
for (int j = 0; j < 26; ++j)
if (((x >> j) & 1) == 0)
merge(x, x ^ (1 << i) | (1 << j)); // 替换字符 i 为 j
}
}
return {groups, maxSize};
}
};
java 解法, 执行用时: 659 ms, 内存消耗: 53.2 MB, 提交时间: 2023-09-04 23:39:11
class Solution {
// 并查集模板（哈希表写法）
HashMap<Integer, Integer> fa = new HashMap<>(), size = new HashMap<>();
int groups, maxSize;
int find(int x) {
if (fa.get(x) != x) fa.put(x, find(fa.get(x)));
return fa.get(x);
}
void merge(int x, int y) {
if (!fa.containsKey(y)) return;
x = find(x);
y = find(y);
if (x == y) return;
fa.put(x, y);
size.put(y, size.get(y) + size.get(x));
maxSize = Math.max(maxSize, size.get(y)); // 维护答案
--groups;
}
public int[] groupStrings(String[] words) {
groups = words.length;
for (var word : words) {
var x = 0;
for (var i = 0; i < word.length(); i++)
x |= 1 << (word.charAt(i) - 'a'); // 计算 word 的二进制表示
fa.put(x, x); // 添加至并查集
size.put(x, size.getOrDefault(x, 0) + 1);
maxSize = Math.max(maxSize, size.get(x)); // 维护答案
if (size.get(x) > 1) --groups;
}
fa.forEach((x, fx) -> {
for (var i = 0; i < 26; i++) {
merge(x, x ^ (1 << i)); // 添加或删除字符 i
if (((x >> i) & 1) == 1)
for (var j = 0; j < 26; ++j)
if (((x >> j) & 1) == 0)
merge(x, x ^ (1 << i) | (1 << j)); // 替换字符 i 为 j
}
});
return new int[]{groups, maxSize};
}
}
python3 解法, 执行用时: 6800 ms, 内存消耗: 26.8 MB, 提交时间: 2023-09-04 23:38:56
class Solution:
def groupStrings(self, words: List[str]) -> List[int]:
# 并查集模板（哈希表写法）
fa, size = {}, defaultdict(int)
groups, max_size = len(words), 0
def find(x: int) -> int:
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
def merge(x: int, y: int):
nonlocal groups, max_size
if y not in fa:
return
x, y = find(x), find(y)
if x == y:
return
fa[x] = y
size[y] += size[x]
max_size = max(max_size, size[y]) # 维护答案
groups -= 1
for word in words:
x = 0
for ch in word:
x |= 1 << (ord(ch) - ord('a')) # 计算 word 的二进制表示
fa[x] = x # 添加至并查集
size[x] += 1
max_size = max(max_size, size[x]) # 维护答案
if size[x] > 1:
groups -= 1
for x in fa: # 枚举所有字符串（二进制表示）
for i in range(26):
merge(x, x ^ (1 << i)) # 添加或删除字符 i
if (x >> i) & 1:
for j in range(26):
if ((x >> j) & 1) == 0:
merge(x, x ^ (1 << i) | (1 << j)) # 替换字符 i 为 j
return [groups, max_size]