LeetCode 题解工作台
相似字符串组
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。 例如， "tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star"…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们可以枚举字符串列表中的任意两个字符串 和 ，由于 和 是字母异位词，因此如果 和 的对应位置字符不同的数量不超过 ，那么 和 是相似的，我们就可以使用并查集将 和 合并，如果合并成功，那么相似字符串组的数量减少 。 最终相似字符串组的数量就是并查集中连通分量的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？
示例 1：
输入：strs = ["tars","rats","arts","star"] 输出：2
示例 2：
输入：strs = ["omv","ovm"] 输出：1
提示：
1 <= strs.length <= 3001 <= strs[i].length <= 300strs[i]只包含小写字母。strs中的所有单词都具有相同的长度，且是彼此的字母异位词。
解题思路
方法一：并查集
我们可以枚举字符串列表中的任意两个字符串 和 ，由于 和 是字母异位词，因此如果 和 的对应位置字符不同的数量不超过 ，那么 和 是相似的，我们就可以使用并查集将 和 合并，如果合并成功，那么相似字符串组的数量减少 。
最终相似字符串组的数量就是并查集中连通分量的数量。
时间复杂度 ，空间复杂度 。其中 和 分别是字符串列表的长度和字符串的长度，而 是 Ackermann 函数的反函数，可以看成是一个很小的常数。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
n, m = len(strs), len(strs[0])
uf = UnionFind(n)
for i, s in enumerate(strs):
for j, t in enumerate(strs[:i]):
if sum(s[k] != t[k] for k in range(m)) <= 2 and uf.union(i, j):
n -= 1
return n
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on approach: naive DFS is O(n^2 * m) for n strings of length m. Union-Find reduces repeated checks, but still requires pairwise similarity verification in worst case. Space complexity is O(n * m) to store parent pointers or visited flags and possible hash signatures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks for an efficient method to count string similarity groups.
- question_mark
Checks if you can identify similarity using at most two swaps correctly.
- question_mark
Wants an optimized union-find or DFS implementation to handle up to 300 strings.
常见陷阱
外企场景- error
Failing to correctly implement the two-letter swap similarity check.
- error
Performing unnecessary full pairwise comparisons without candidate reduction.
- error
Merging groups incorrectly, leading to undercounting or overcounting groups.
进阶变体
外企场景- arrow_right_alt
Allowing similarity defined by one-letter swap only.
- arrow_right_alt
Strings may have different lengths requiring substring comparisons.
- arrow_right_alt
Counting largest group size instead of total number of groups.