839. Similar String Groups
如果 string A 可以交换某两个字符的顺序变成 string B
那 A 和 B 就是相似的
similar group 代表这个 group 中任意两个 string A B 都能有以下关系:
A 和 A1 相似，A1 和 A2 相似，......，AN 和 B 相似
同时 A1~AN 必须在 similar group 里
好难讲喔肏 反正就是如果画成 graph，两点有 edge 代表相似
similar group 就是 connected component
Example 1:
Input: strs = ["tars","rats","arts","star"]
Output: 2
Example 2:
Input: strs = ["omv","ovm"]
Output: 1
思路:
1.用 disjoint set 吧 有 edge 的就并在一起
枚举 strs[i] 和 strs[j] 看他们是不是相似
O(n^2)次检查*(检查花费O(n)+union)
感觉不会过 真奇怪
class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
def check(a, b):
diff = 0
for i in range(len(a)):
diff += (a[i] != b[i])
if diff > 2:
return False
return True
n = len(strs)
root = list(range(n))
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
for i in range(n):
for j in range(i+1, n):
a, b = strs[i], strs[j]
if check(a, b):
ra, rb = find(i), find(j)
root[ra] = rb
return sum([root[i] == i for i in range(n)])
随便啦

n^3啊哈

好强 会过吧 这题range那么小