Сложность: hard
Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X.
Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.
Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?
Пример:
Input: strs = ["tars","rats","arts","star"]
Output: 2
👨💻 Алгоритм:
1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n.
2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи.
3⃣Верните количество оставшихся групп.
😎 Решение:
class UnionFind {
var parent: [Int]
var rank: [Int]
init(size: Int) {
parent = Array(0..<size)
rank = [Int](repeating: 0, count: size)
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) {
let xset = find(x)
let yset = find(y)
if xset != yset {
if rank[xset] < rank[yset] {
parent[xset] = yset
} else if rank[xset] > rank[yset] {
parent[yset] = xset
} else {
parent[yset] = xset
rank[xset] += 1
}
}
}
}
class Solution {
func isSimilar(_ a: String, _ b: String) -> Bool {
let aArray = Array(a)
let bArray = Array(b)
var diff = 0
for i in 0..<a.count {
if aArray[i] != bArray[i] {
diff += 1
}
}
return diff == 0 || diff == 2
}
func numSimilarGroups(_ strs: [String]) -> Int {
let n = strs.count
let dsu = UnionFind(size: n)
var count = n
for i in 0..<n {
for j in i+1..<n {
if isSimilar(strs[i], strs[j]) && dsu.find(i) != dsu.find(j) {
count -= 1
dsu.union(i, j)
}
}
}
return count
}
}Ставь 👍 и забирай 📚 Базу знаний