MediumRating 1638

990. Satisfiability of Equality Equations

arraystringunion-findgraph

在 LeetCode 上作答 ↗

解題說明

Satisfiability of Equality Equations

題目描述：給定一個字串陣列 equations，每個字串格式為 "a==b" 或 "a!=b"，其中 a 和 b 為小寫字母（代表變數）。判斷是否存在一種變數賦值，使得所有方程同時成立。

解題思路：

本題是典型的 Union-Find 應用：等式建立等價類，不等式驗證矛盾。

關鍵觀察：== 具有傳遞性（a==b 且 b==c 則 a==c），這正是 Union-Find 最擅長處理的場景；!= 則表示兩個變數不能在同一等價類中。

兩階段處理：

第一階段（建立等價類）：遍歷所有 == 方程，將兩側字母 union 在一起。
第二階段（驗證不等式）：遍歷所有 != 方程，若兩側字母的根相同（屬於同一等價類），則矛盾，回傳 false。

變數節點設計：字母只有 26 個（a-z），以 ch - 'a' 為索引，建立大小為 26 的 Union-Find 陣列，空間和時間都是 O(26) = O(1)。

注意：必須先處理完所有 ==，再處理所有 !=。若交錯處理，可能漏掉傳遞關係。例如 a==b、b==c、a!=c，若在 a==b 和 a!=c 之間就判斷，此時 a 和 c 還不在同一分量中，會誤判為 true。

C++ 解法

複雜度分析

時間複雜度：O(n · α(26)) ≈ O(n) — 遍歷 n 個方程兩次；Union-Find 操作的節點數固定為 26，每次 find/union 為 O(α(26)) ≈ O(1) 常數。整體線性 O(n)。

空間複雜度：O(26) = O(1) — parent 和 rank 陣列固定大小 26，與輸入規模無關。

虛擬碼

1. Initialize parent[i]=i, rank[i]=0 for i in [0,26)
2. Phase 1 - Union all '==' equations:
   For each equation eq:
     If eq[1] == '=':  // format "a==b"
       unite(eq[0]-'a', eq[3]-'a')
3. Phase 2 - Check all '!=' equations:
   For each equation eq:
     If eq[1] == '!':
       If find(eq[0]-'a') == find(eq[3]-'a'):
         Return false  // a and b in same equivalence class but a!=b
4. Return true

其他解法

有向圖 + BFS/DFS O(n + 26²)：將 == 關係建成無向圖（26 個節點），用 BFS/DFS 求連通分量並標記每個字母的分組，再驗證 != 對。優點是不需要 Union-Find 知識，思路更直觀；缺點是建圖 + BFS 的常數略大，且程式碼比 Union-Find 版稍長。兩者複雜度相當，都是 O(n)。

拓撲排序 / 2-SAT：若方程變得更複雜（如包含不等式鏈和推導），可以引入 2-SAT 或約束傳播（constraint propagation）。對本題來說是殺雞用牛刀，實作過重，無實際優勢。

直接雜湊分組：用 unordered_map<char,char> 暴力維護等價類（Union 時遍歷所有鍵更新），再驗證 !=。優點是不需要 find/union 函數；缺點是在最壞情況下每次 merge 要更新 O(26) 個鍵，且沒有路徑壓縮，不如標準 Union-Find 簡潔。

延伸思考

若方程中的變數不是單個字母，而是任意字串（例如 "foo==bar"），如何修改資料結構以保持同樣的時間複雜度？
若同時存在 <、<=、>、>= 等比較運算子，Union-Find 是否仍然適用？若不適用，應使用什麼方法（提示：差分約束 Bellman-Ford）？
本題兩階段處理（先 == 後 !=）的順序是否可以顛倒？若先處理 != 再處理 ==，會出現什麼問題？請舉反例說明。