Сложность: 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:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
class Solution:
def isSimilar(self, a, b):
diff = sum(1 for x, y in zip(a, b) if x != y)
return diff == 0 or diff == 2
def numSimilarGroups(self, strs):
n = len(strs)
dsu = UnionFind(n)
count = n
for i in range(n):
for j in range(i + 1, n):
if self.isSimilar(strs[i], strs[j]) and dsu.find(i) != dsu.find(j):
count -= 1
dsu.union(i, j)
return count
Ставь 👍 и забирай 📚 Базу знаний