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)])
隨便啦