题目难度: 困难
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给定一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个 字母异位词 。请问 strs 中有多少个相似字符串组？
字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
示例 1：
- 输入：strs = ["tars","rats","arts","star"]
- 输出：2
示例 2：
- 输入：strs = ["omv","ovm"]
- 输出：1
提示：
- 1 <= strs.length <= 300
- 1 <= strs[i].length <= 300
- strs[i] 只包含小写字母。
- strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。
题目思考
- 可以使用什么数据结构或算法来解决?
解决方案
- 分析题目, 不难发现这个问题包含两个子问题: 1. 判断两个字符串是否相似; 2. 将相似字符串分组
- 判断两个字符串是否相似比较简单, 只需要遍历两个字符串, 查看是否有且仅有两个位置的字符不同且交换后相同即可
- 而将相似字符串分组, 可以使用并查集的思路, 将相似字符串放在同一个集合中, 我之前还写过一个并查集的系列, 感兴趣的同学在我的公众号聊天框中回复 并查集 就能看到了
- 具体步骤如下:
- 首先我们需要定义一个字典 pre,
pre[s]表示 s 的祖先, 如果两个元素具有相同祖先, 就表示它们在同一个集合中. 可以把祖先pre[s]想象成一个树的根节点, 那么 s 就是树中的一个节点(可能是根节点本身) - 然后定义一个 find 方法, 查找当前元素的祖先, 如果祖先不存在的话就把自身当做祖先. 这里用到了路径压缩的优化, 就是说当发现自己的祖先不是自身的时候, 就尝试把自己的祖先设置为自己的当前祖先的祖先, 从而降低树的高度, 加快之后的查找过程.
- 最后定义一个 union 方法, 用于合并两个元素. 这里的思路也很简单, 就是找到各自的祖先, 然后将其中一个的祖先的祖先设置为另外一个祖先即可, 等于就把两个树合并在了一起
- 首先我们需要定义一个字典 pre,
- 我们通过两重循环遍历所有字符串, 如果当前字符串对相似, 就将其合并, 最终查找有多少个不同的祖先, 即为相似字符串组的个数
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(N^2*(C+logN)): N 是字符串数目, C 是每个字符串的平均长度, 我们需要两重循环遍历所有字符串对(O(N^2)), 然后对每一对检查其是否相似(O(C)), 相似的话需要合并(O(logN)), 所以总时间复杂度就是O(N^2*(C+logN)) - 空间复杂度
O(NC): 并查集需要存 N 个字符串, 每个字符串的平均长度是 C
代码
class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
### 并查集+双重循环找相似
pre = {}
def find(s):
# 查找s的祖先, 顺便进行路径压缩
if s not in pre:
# 当前字符串还不在pre字典中, 就初始化其祖先为字符串本身
pre[s] = s
elif pre[s] != s:
# 当前字符串和祖先字符串不一样, 尝试路径压缩
pre[s] = find(pre[s])
return pre[s]
def union(s1, s2):
# 将两个字符串进行合并
pre[find(s1)] = find(s2)
def isSimilar(s1, s2):
# 判断s1和s2是否相似
# pc1和pc2是上一对不同的字符
pc1, pc2 = "", ""
diffCnt = 0
for c1, c2 in zip(s1, s2):
if c1 != c2:
diffCnt += 1
if diffCnt > 2:
# 超过两个不同
return False
if diffCnt == 2 and (c1 != pc2 or c2 != pc1):
# 不能相互替换
return False
pc1 = c1
pc2 = c2
# 最终需要满足恰好有两个位置不同
return diffCnt == 2
for i in range(len(strs)):
for j in range(i + 1, len(strs)):
s1, s2 = strs[i], strs[j]
if isSimilar(s1, s2):
# 当前字符串对相似, 将其合并
union(s1, s2)
# 查找有多少个不同的祖先, 即为相似字符串组的个数
v = set()
for s in strs:
v.add(find(s))
return len(v)
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号