839. Similar String Groups

Similar String Groups

題目描述：給定一個字串陣列 strs，所有字串都是彼此的 anagram（包含相同字母）。若兩個字串相似，則定義為：它們完全相同，或者恰好在兩個位置上字母不同（交換這兩個位置的字母可使其互相轉換）。相似關係具有傳遞性，求這個陣列中共有幾組相似字串群（連通分量）。

解題思路：

本題的核心是建立圖的連通分量，因此 Union-Find 非常適合。

相似性判斷函數 isSimilar(a, b)：

• 遍歷每個位置，統計不同字元的個數 diff。
• 若 diff == 0（完全相同）→ 相似。
• 若 diff == 2（恰好兩個位置不同）→ 相似（因為都是 anagram，只要有 2 個不同位置就必然能交換）。
• 若 diff > 2 → 不相似（提前剪枝）。

主流程：

1. 初始化 Union-Find，n 個節點，初始 components = n。
2. 對所有字串對 (i, j)（i < j）執行相似性檢查，相似則 union(i, j)，components--（若不同分量）。
3. 最終回傳 components。

複雜度分析：字串長度為 L，共 n 條字串，需比較 O(n²) 對，每次比較 O(L)，整體 O(n²·L)。n 最大 300，L 最大 300，共約 2.7×10⁷ 次操作，可接受。

時間複雜度：O(n²·L·α(n)) ≈ O(n²·L) — 共 n(n-1)/2 對字串，每對比較長度 L 的字串（O(L)），Union-Find 操作 O(α(n)) 接近常數。n 和 L 最大均為 300，約 1.35×10⁷ 次字元比較。

空間複雜度：O(n) — parent 和 rank 陣列各長 n，不需要額外儲存圖的邊。

BFS/DFS 建圖 O(n²·L)：先預建鄰接表（相似的字串對連邊），再用 BFS/DFS 統計連通分量數。與 Union-Find 時間複雜度相同，但需要 O(n²) 額外空間儲存邊，且 BFS/DFS 的常數略大。Union-Find 不需要預建圖，更省空間。

Trie / 字典樹優化：若字串長度 L 很大但字母表小，可以將字串的所有「合法鄰居」（交換兩個位置後的字串）插入 Trie，並在其中查找當前字串。優點是對 L 大、n 小的情況更快；缺點是實作複雜，且本題 n 和 L 均有限（≤300），暴力 O(n²·L) 已足夠。

剪枝優化：在 isSimilar 中加入提前返回（diff > 2 時立即 return false），實際執行中大部分不相似對只需掃描少數位置即可判斷，平均比較次數遠少於 L，提升常數因子。此外，若兩個字串已在同一連通分量（find(i) == find(j)），可跳過相似性檢查（但此優化在 n 小時收益有限）。

1. 若「相似」的定義放寬到「最多 k 個位置不同」（k 可以大於 2），判斷函數如何修改？整體複雜度是否改變？
2. 若字串不保證互為 anagram，相似性判斷應如何調整？（需先驗證字母頻率相同）
3. 本題若改為「求最小操作次數使所有字串相同」（每次操作為交換某字串的兩個字元），這是什麼類型的問題？與連通分量有何關聯？