leetCode-990. 等式方程的可满足性-一一网

990. 等式方程的可满足性-链接

描述

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

示例 1：
输入：[“a==b”,”b!=a”]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：
输入：[“b==a”,”a==b”]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3：
输入：[“a==b”,”b==c”,”a==c”]
输出：true

示例 4：
输入：[“a==b”,”b!=c”,”c==a”]
输出：false

示例 5：
输入：[“c==c”,”b==d”,”x!=z”]
输出：true

提示：
1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 ‘=’，要么是 ‘!’
equations[i][2] 是 ‘=’

题解

我们可以将每个方程式中的变量看做成某个节点，然后把相等的两个节点放到同一个集合里面，又因为相等具有传递性，既如果 a == b 并且 b == c 那么 a == c ，因此我们可以首先遍历所有的等式，把互相相等的放到同一个集合里面，再遍历不等式，如果他们属于同一个集合，则与相等矛盾，不能满足条件。返回 false ,否则返回true .
而上面的集合，用并查集实现是最为方便。那么什么是并查集呢？

在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
合并：将两个集合合并为一个。
添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。
由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。

具体实现

首先遍历所有的等式，创建一个并查集。并将等式中的变量进行合并。然后遍历所有的不等式，分别查找变量所在的集合，若同属于一个集合，则返回false，否则返回true

class Solution {
    func equationsPossible(_ equations: [String]) -> Bool {
        var notEquals = [(Int, Int)]()
        let unionFind = UnionFind(count: 26)
        for equation in equations {
            let a = Int(equation.first!.unicodeScalars.first!.value - 97)
            let b = Int(equation.last!.unicodeScalars.first!.value - 97)
            let isEqual = equation[equation.index(after: equation.startIndex)] == "="
            if isEqual {
                unionFind.union(num1: a, num2: b)
            } else {
                notEquals.append((a,b))
            }
        }
        for (a, b) in notEquals {
            if unionFind.find(num: a) == unionFind.find(num: b) {
                return false
            }
        }
        return true
    }
}

private class UnionFind {
    private var parent: [Int]
    init(count: Int) {
        self.parent = Array(repeating: 0, count: count)
        for i in 0..<count {
            self.parent[i] = i
        }
    }
    
    func union(num1: Int, num2: Int) {
        guard num1 != num2 else {
            return
        }
        let fNum1 = find(num: num1)
        let fNum2 = find(num: num2)
        guard fNum1 != fNum2 else {
            return
        }
        parent[fNum1] = fNum2
    }
    
    func find(num: Int) -> Int {
        if num != parent[num] {
            parent[num] = find(num: parent[num])
        }
        return parent[num]
    }
}
复制代码