LeetCode 相似字符串组题解

LeetCode 相似字符串组题解题目描述如果两个字符串完全相同或者只有一对字符不同则它们是相似的。给定一个字符串数组返回相似字符串组的数量。示例输入strs [tars,rats,arts,star]输出2解题思路方法并查集思路使用并查集来解决这个问题。遍历所有字符串对如果它们相似则合并。最后统计集合数量。复杂度分析时间复杂度O(n^2 * L)。空间复杂度O(n)。代码实现class UnionFind: def __init__(self, n): self.parent list(range(n)) def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py self.find(x), self.find(y) if px py: return self.parent[px] py def are_similar(s1, s2): diff [] for i in range(len(s1)): if s1[i] ! s2[i]: diff.append(i) if len(diff) 2: return False return len(diff) 0 or (len(diff) 2 and s1[diff[0]] s2[diff[1]] and s1[diff[1]] s2[diff[0]]) def num_similar_groups(strs): n len(strs) uf UnionFind(n) for i in range(n): for j in range(i 1, n): if are_similar(strs[i], strs[j]): uf.union(i, j) return sum(1 for i in range(n) if uf.find(i) i) # 测试 def test_num_similar_groups(): strs [tars, rats, arts, star] print(num_similar_groups(strs)) # 输出2 if __name__ __main__: test_num_similar_groups()总结相似字符串组是并查集的典型应用将相似的字符串合并最后统计集合数量。