Satisfiability of Equality Equations

Share

Given equations like "a==b" or "a!=b", determine if all equations can be satisfied simultaneously.

Example 1
Input: ["a==b","b!=a"] → Output: false
Example 2
Input: ["b==a","a==b"] → Output: true

Solution Approach

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.
Java
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)