剑指 Offer II 117. 相似的字符串
2022-08-03 本文已影响0人
邦_
并查集，基于rank优化 + 路径减半
class Solution {
class MyUnionFind {
var parents = [Int]()
var ranks : [Int]
init(_ capacity:Int){
ranks = Array.init(repeating: 1, count: capacity)
for i in 0..<capacity {
parents.append(i)
}
}
func find(_ v:Int)-> Int{
var temp = v
//路径减半
while parents[temp] != temp {
parents[temp] = parents[parents[temp]]
temp = parents[temp]
}
return temp
}
func union(_ v1:Int,_ v2:Int){
let p1 = find(v1)
let p2 = find(v2)
if p1 == p2 {
return
}
let r1 = ranks[p1]
let r2 = ranks[p2]
if r1 < r2 {
parents[p1] = p2
}else if r1 > r2 {
parents[p2] = p1
}else {
parents[p1] = p2
ranks[p2] += 1
}
}
func isSame(_ v1:Int,_ v2:Int)-> Bool{
return find(v1) == find(v2)
}
}
func numSimilarGroups(_ strs: [String]) -> Int {
var res = 0
let len = strs.count
//初始化并查集
let uf = MyUnionFind(len)
for i in 0..<len {
for j in i+1..<len{
if uf.isSame(i, j){
continue
}
if similar(strs[i], strs[j]){
uf.union(i, j)
}
}
}
for i in 0..<len {
if uf.parents[i] == i {
res += 1
}
}
return res
}
func similar(_ str:String,_ str1:String) ->Bool {
var dif = 0
let len = str.count
let array1 = Array(str)
let array2 = Array(str1)
for i in 0..<len {
if array1[i] != array2[i] {
dif += 1
if dif > 2 {
return false
}
}
}
return true
}
}
