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: 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: equations = [“ba","ab”]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
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.
就是个 graph 的问题， 如果节点 a 与节点 b 是联通的(a == b), 同时又要求 a 与 b 不能联通(a != b), 则返回 false， 其他情况返回 true。 具体的办法还是用 union find 的方法， 我们只对==做 union， 然后用!=来做检查， 只要没有两个不等式左右两边的节点具有同一个 parent， 则返回 true
impl Solution {
fn find(idx: usize, parents: &mut Vec<usize>) -> usize {
if parents[idx] == idx {
return idx;
}
let parent = Solution::find(parents[idx], parents);
parents[idx] = parent;
parent
}
fn union(a: usize, b: usize, parents: &mut Vec<usize>) {
let a_parent = Solution::find(a, parents);
let b_parent = Solution::find(b, parents);
parents[b_parent] = a_parent;
}
pub fn equations_possible(equations: Vec<String>) -> bool {
let mut parents: Vec<usize> = (0..26).into_iter().collect();
let mut not_equals = Vec::new();
for equation in equations {
let components: Vec<char> = equation.chars().collect();
if components[1] == '=' {
Solution::union(
components[0] as usize - 97,
components[3] as usize - 97,
&mut parents,
);
continue;
}
not_equals.push((components[0] as usize - 97, components[3] as usize - 97));
}
for (a, b) in not_equals {
let a_parent = Solution::find(a, &mut parents);
let b_parent = Solution::find(b, &mut parents);
if a_parent == b_parent {
return false;
}
}
true
}
}