Published: Sep 26, 2022
This is a graph problem since the equations define the relations between two node. The equations will create a directed cycle graph. The depth-first search or union find will give us the answer. In this case, the problem is related to groups, not like paths. For this reason, the solution here took the union find approach.
You are given an array of strings
equationsthat represent relationships between variables where each string
equations[i]is of length 4 and takes one of two different forms:
y[i]are lowercase letters (not necessarily different) that represent one-letter variable names.
trueif it is possible to assign integers to variable names so as to satisfy all the given equations, or
1 <= equations.length <= 500
equations[i].length == 4
equations[i]is a lowercase letter
equations[i]is either ‘=’ or ‘!’
equations[i]is a lowercase letter.
Example 1 Input: equations = ["a==b","b!=a"] Output: false
Example 2 Input: equations = ["b==a","a==b"] Output: true
Example 3 Input: ["a==b","b!=c","c==a"] Output: false
The approach here is a union find.
So, two functions, find and union were defined first.
Then, the solution took 2 step traversal of the equations (relations).
== equations to union groups.
Next, pick up
!= equations to test two groups are not in the same group.
class SatisfiabilityOfEqualityEquations: def equationsPossible(self, equations: List[str]) -> bool: groups = [i for i in range(26)] def atoi(ch): return ord(ch) - ord('a') def find(x): while x != groups[x]: x = groups[x] return x def union(x, y): group_x, group_y = find(x), find(y) if group_x < group_y: groups[group_y] = group_x else: groups[group_x] = group_y for eq in equations: if eq == '=': x, y = atoi(eq), atoi(eq) union(x, y) for eq in equations: if eq == '!': x, y = atoi(eq), atoi(eq) if find(x) == find(y): return False return True
O(1)– auxiliary array has always length 26, constant