Given equations like "a==b" or "a!=b", determine if all equations can be satisfied simultaneously.
Input: ["a==b","b!=a"] → Output: falseInput: ["b==a","a==b"] → Output: true
Union-Find: first process all == equations to union variables. Then check != equations — if two variables are in the same component, return false.
- Union-Find over 26 letters.
- Pass 1: for all "==" equations, union the two characters.
- Pass 2: for all "!=" equations, if find(a)==find(b) return false.
- Return true.
class Solution {
int[] parent = new int[26];
public boolean equationsPossible(String[] equations) {
for (int i = 0; i < 26; i++) parent[i] = i;
for (String eq : equations)
if (eq.charAt(1) == '=') union(eq.charAt(0)-'a', eq.charAt(3)-'a');
for (String eq : equations)
if (eq.charAt(1) == '!' && find(eq.charAt(0)-'a') == find(eq.charAt(3)-'a')) return false;
return true;
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
private void union(int a, int b) { parent[find(a)] = find(b); }
}
- Time Complexity: O(N * alpha(26)) ≈ O(N)
- Space Complexity: O(26) = O(1)