839. Similar String Groups

解題說明

C++ 解法

複雜度分析

虛擬碼

1. Initialize Union-Find: parent[i]=i, rank[i]=0, components=n
2. For i in [0, n):
   For j in [i+1, n):
     If isSimilar(strs[i], strs[j]):
       If unite(i, j) returns true: components--
3. Return components

isSimilar(a, b):
  diff = 0
  For each position k:
    If a[k] != b[k]: diff++
    If diff > 2: return false  // early termination
  Return diff == 0 or diff == 2

unite(a, b):
  ra = find(a), rb = find(b)
  If ra == rb: return false
  Merge by rank; return true

其他解法

延伸思考