Similar String Groups
Intuition
Solution
class Solution:
def similar(self, A, i, j):
diff = 0
for c1, c2 in zip(A[i], A[j]):
if c1 != c2:
diff += 1
if diff > 2:
return False
return True
def numSimilarGroups(self, A: List[str]) -> int:
A = list(set(A))
if not A:
return 0
W = len(A[0])
N = len(A)
dsu = DSU(N)
if N < W * W:
for i in range(N):
for j in range(i + 1, N):
if self.similar(A, i, j):
dsu.union(i, j)
else:
indexes = {c: i for i, c in enumerate(A)}
for i, w in enumerate(A):
for p in range(W):
for q in range(p + 1, W):
tmp = w[:p] + w[q] + w[p + 1:q] + w[p] + w[q + 1:]
if tmp in indexes:
j = indexes[tmp]
dsu.union(i, j)
return dsu.count()