LeetCode 题解工作台
字符串分组
给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。 words 中任意一个子串中，每个字母都至多只出现一次。 如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ： 往 s1 的字母集合中添加一个字母。 从…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 并查集
答案摘要
class Solution: def groupStrings(self, words: List[str]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
给你一个下标从 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]中每个字母最多只出现一次。
解题思路
方法一：状态压缩（位运算） + 并查集
class Solution:
def groupStrings(self, words: List[str]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
nonlocal mx, n
if b not in p:
return
pa, pb = find(a), find(b)
if pa == pb:
return
p[pa] = pb
size[pb] += size[pa]
mx = max(mx, size[pb])
n -= 1
p = {}
size = Counter()
n = len(words)
mx = 0
for word in words:
x = 0
for c in word:
x |= 1 << (ord(c) - ord('a'))
p[x] = x
size[x] += 1
mx = max(mx, size[x])
if size[x] > 1:
n -= 1
for x in p.keys():
for i in range(26):
union(x, x ^ (1 << i))
if (x >> i) & 1:
for j in range(26):
if ((x >> j) & 1) == 0:
union(x, x ^ (1 << i) | (1 << j))
return [n, mx]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate's ability to apply graph theory or union-find for problem-solving.
- question_mark
Knowledge of bit manipulation and its application in optimizing string-based problems.
- question_mark
Understanding of time and space complexity trade-offs when choosing between union-find and bit manipulation.
常见陷阱
外企场景- error
Not considering all possible connections between words, leading to incorrect groupings.
- error
Overcomplicating the solution by trying to implement complex graph algorithms when a simpler union-find approach suffices.
- error
Failure to properly handle edge cases, such as words with no connections or all words being connected.
进阶变体
外企场景- arrow_right_alt
Adding constraints where some strings may contain more than 26 characters.
- arrow_right_alt
Modifying the problem to account for case-insensitive letter transformations.
- arrow_right_alt
Allowing a larger set of operations, such as swapping letters, instead of just adding, deleting, or replacing.