【LeetCode】839、相似字符串组

【LeetCode】839、相似字符串组

一、并查集

1.1 并查集

求共有几组, 联想到并查集, 即并查集有几个集合

字符串相似: 相差0个字符, 或2个字符

其中所有字符串长度都相同, 是比较方便处理的

// go
var sets int
var father [301]int

func numSimilarGroups(strs []string) int {
    n := len(strs)
    m := len(strs[0])
    build(n)
    for i := range n {
        for j := i+1; j < n; j++ {
            if find(i) == find(j) {continue} // 若已在一个集合中了, 而无需union
            diff := 0 // str[i] 和 str[j] 不同的字符数量
            for k := 0; k < m && diff < 3; k++ {
                if strs[i][k] != strs[j][k] {diff++}
            }
            if diff == 0 || diff == 2 {
                union(i, j)
            }
        }
    }
    return sets
}

func build(n int) {
    for i := range n {
        father[i] = i
    }
    sets = n
}

func find(i int) int {
    if father[i] != i {
        father[i] = find(father[i])
    }
    return father[i]
}

func union(a, b int) {
    fa, fb := find(a), find(b)
    if fa != fb {
        father[fa] = fb
        sets--
    }
}

参考左神 并查集

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts