LeetCode每日一题(990. Satisfiability of Equality Equations)

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
    }
}