【LeetCode】839、相似字符串組

一、并查集

1.1 并查集

求共有幾組, 聯想到并查集, 即并查集有幾個集合

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

其中所有字符串長度都相同, 是比較方便處理的

// go
var sets int
var father [301]intfunc 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} // 若已在一個集合中了, 而無需uniondiff := 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] = fbsets--}
}

參考左神 并查集

二、多語言解法

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

// cpp

// go 同上

# python

// rust

// js

// ts