剑指 Offer II 117. 相似的字符串

并查集，基于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
        
    }
}