動機
做兩遍union find!!
Problem
You are given an array of strings equations
that represent relationships between variables where each string equations[i]
is of length 4
and takes one of two different forms: "xi==yi"
or "xi!=yi"
.Here, xi
and yi
are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true
if it is possible to assign integers to variable names so as to satisfy all the given equations, or false
otherwise.
Example 1:
Input: equations = ["a==b","b!=a"]Output: falseExplanation: 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: equations = ["b==a","a==b"]Output: trueExplanation: We could assign a = 1 and b = 1 to satisfy both equations.
Example 3:
Input: equations = ["a==b","b==c","a==c"]Output: true
Example 4:
Input: equations = ["a==b","b!=c","c==a"]Output: false
Example 5:
Input: equations = ["c==c","b==d","x!=z"]Output: true
Constraints:
1 <= equations.length <= 500
equations[i].length == 4
equations[i][0]
is a lowercase letter.equations[i][1]
is either'='
or'!'
.equations[i][2]
is'='
.equations[i][3]
is a lowercase letter.
Sol
用union find把==
串起來
但是就算加rank還是會遇到["a==b","e==c","b==c","a!=e"]
這種不小心接到小的item的case
class Solution:
def equationsPossible(self, es: List[str]) -> bool:
var = set()
[(var.add(e[0]), var.add(e[3])) for e in es]
noteq = [(e[0],e[3]) for e in es if e[1] == "!"]
eq = [(e[0],e[3]) for e in es if e[1] == "="]
uf = {v:v for v in var}
rank = defaultdict(int)
def find(v):
while v != uf[v]:
uf[v] = uf[uf[v]]
v = uf[v]
return v
def union(a,b):
x,y = find(a), find(b)
if rank[x] >= rank[y]:
uf[b] = a
rank[a] += 1
else:
uf[a] = b
rank[b] += 1
[union(a,b) for a,b in eq]
#print(uf, noteq)
return all(find(a) != find(b) for a,b in noteq)