Satisfiability of Equality Equations

990. Satisfiability of Equality Equations

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: “a==b” or “a!=b”. Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.
Example 2:

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
Example 3:

Input: ["a==b","b==c","a==c"]
Output: true
Example 4:

Input: ["a==b","b!=c","c==a"]
Output: false
Example 5:

Input: ["c==c","b==d","x!=z"]
Output: true

Problem Analysis

We have 26 nodes in the graph. All “==” equations represent the connection in the graph. The connected nodes should be in the same union or set.

Then we check all inequations. Two unequal nodes should be in a different union or set.

Algorithm Analysis

Use two Sets

Traversing the equation of == and put both first and second character into the set. Then, traverse the equation of != and check if first is inside the set of second and second is inside the set of first.

Union Find

First, pass all == equations. Union equal letters together
Now we know which letters must equal to the others. Second pass all != inequations, Check if there are any contradict happens.

Time Complexity

Use Two Set - O(N*K)

Union Find - O(N)

Code Implementation - Using Two Sets

class Solution {
    public boolean equationsPossible(String[] equations) {
        Map<Character, Set<Character>> map = new HashMap<>();
        for(String equation : equations) {
            if(equation.charAt(1) == '!') continue;
            
            char first = equation.charAt(0);
            char second = equation.charAt(3);
            
            Set<Character> set1 = map.getOrDefault(first, new HashSet<>());
            set1.add(first);
            set1.add(second);
            Set<Character> set2 = map.getOrDefault(second, new HashSet<>());
            for(char c : set2) {
                set1.add(c);
            }
            map.put(first, set1);
            map.put(second, set1);
        }
        
        for(String equation : equations) {
            if(equation.charAt(1) == '=') continue;   
            
            char first = equation.charAt(0);
            char second = equation.charAt(3);
            
            if(first == second) return false;
            
            if(map.getOrDefault(first, new HashSet<>()).contains(second)) {
                return false;
            }
            
            if(map.getOrDefault(second, new HashSet<>()).contains(first)) {
                return false;
            }
        }
        return true;
    }
}

Code Implementation - Union Find algorithm

class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);
        
        for(String equation : equations) {
            if(equation.charAt(1) == '!') continue;
            uf.union(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
        }
        
        for(String equation : equations) {
            if(equation.charAt(1) == '=') continue;
            int setA = uf.find(equation.charAt(0) - 'a');
            int setB = uf.find(equation.charAt(3) - 'a');
            if(setA == setB) {
                return false;
            }
        }
        return true;
    }
}

class UnionFind {
    private int[] parents;
    
    public UnionFind(int n) {
        parents = new int[n];
        for(int i = 0; i < n; i++) {
            parents[i] = i;
        }
    }
    
    public int find(int x) {
        if(parents[x] == x) {
            return x;
        }
        /* Find the aprent of this node */
        return find(parents[x]);
    }
    
    public void union(int a, int b) {
        int setA = find(a);
        int setB = find(b);
        if(setA != setB) {
            parents[setA] = setB; /* Connect setA and setB together */
        }
    }
}

Satisfiability of Equality Equations

Leetcode - No. 990