Satisfiability of Equality Equations

LeetCode Q 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

Note:

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] and equations[i][3] are lowercase letters
• equations[i][1] is either ‘=’ or ‘!’
• equations[i][2] is ‘=’

Solution

Solution 1: Disjoint Set / Union Find

Code:

class UnionFindSet {
	int[] parent;
	public UnionFindSet (int size) {
		this.parent = new int[size];
		for (int i = 0; i < size; i++) 
			parent[i] = i;
	}
	
	public int find (int x) {
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}
	
	public void union (int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) parent[px] = py;
	}
}

public boolean equationsPossible(String[] equations) {
	UnionFindSet ufs = new UnionFindSet(26);
	for (String equ: equations) {
		if (equ.charAt(1) == '=') 
			ufs.union(equ.charAt(0) - 'a', equ.charAt(3) - 'a');
	}
	
	for (String equ: equations) {
		if (equ.charAt(1) == '!') 
			if (ufs.find(equ.charAt(0) - 'a') == ufs.find(equ.charAt(3) - 'a'))
				return false;
	}
	
	return true;
}