990 Satisfiability of Equality Equations

Comments

Problem Setting

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.

Solution from superluminal

In [26]:
# https://leetcode.com/superluminal/
class Solution(object):
    def equationsPossible(self, equations):
        """
        :type equations: List[str]
        :rtype: bool
        """
        uf = {}
        def find(x):
            if x not in uf: uf[x] = x
            s = []
            while uf[x] != x:
                s.append(x)
                x = uf[x]
            for y in s: uf[y] = x
            return x
        for eq in equations:
            if '==' not in eq: continue
            a, b = find(eq[0]), find(eq[-1])
            # should compare rank but whatever
            uf[a] = b
        for eq in equations:
            if '!=' not in eq: continue
            a, b = find(eq[0]), find(eq[-1])
            if a == b: return False
        return True

Step 1-1

  • create function find
    • determine if x exist in a dictionray uf
    • If it does not exist, it will be stored as the key and the value
In [27]:
uf = {}
def find(x):
    if x not in uf: uf[x] = x
    print(f'uf: {uf}')

    return x
In [28]:
find('a')

uf: {'a': 'a'}
Out[28]:
'a'
In [29]:
find('b')

uf: {'a': 'a', 'b': 'b'}
Out[29]:
'b'

Step 1-2

  • Keep append x to list s until the value and key is equal
In [18]:
uf = {}
def find(x):
    if x not in uf: uf[x] = x
    s = []
    print(f'uf: {uf}')
    while uf[x] != x:
        print(f'uf[x] != x: {x}')
        s.append(x)
        x = uf[x]
    for y in s: uf[y] = x
    return x
In [24]:
eq = "a==b"
a, b = find(eq[0]), find(eq[-1])
print(f'return value (a, b): {a, b}')
print(f'uf[a] = b: {uf[a], b}')
uf[a] = b
print(f'uf: {uf}')

uf: {'a': 'a', 'b': 'b', 'c': 'c'}
uf: {'a': 'a', 'b': 'b', 'c': 'c'}
return value (a, b): ('a', 'b')
uf[a] = b: ('a', 'b')
uf: {'a': 'b', 'b': 'b', 'c': 'c'}
In [25]:
eq = "b==c"
a, b = find(eq[0]), find(eq[-1])
print(f'uf[a] = b: {uf[a], b}')
uf[a] = b
print(f'uf: {uf}')

uf: {'a': 'b', 'b': 'b', 'c': 'c'}
uf: {'a': 'b', 'b': 'b', 'c': 'c'}
uf[a] = b: ('b', 'c')
uf: {'a': 'b', 'b': 'c', 'c': 'c'}
In [ ]:
eq = "b==c"
a, b = find(eq[0]), find(eq[-1])
print(a, b)

Comments

Comments powered by Disqus