990. Satisfiability of Equality Equations

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.

Example 3:

Input: ["a==b","b==c","a==c"]
Output: true

Example 4:

Input: ["a==b","b!=c","c==a"]
Output: false

Example 5:

Input: ["c==c","b==d","x!=z"]
Output: true

Note:

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] and equations[i][3] are lowercase letters
  4. equations[i][1] is either '=' or '!'
  5. equations[i][2] is '='

这道题给了一系列简单的公式,某两个字母相等或者不等,然后问给的这些公式会不会产生矛盾,就比如说一个是 a==b,另一个是 a!=b,这就是矛盾了。或者有些更复杂的,相等是可以传递的,比如例子4中,就是一种比较复杂的情况。这里比较直接的一种解法就是建立无向图来做,每个字母都可以当作一个结点,然后等号就表示相连的结点。开始时先跳过所有的不等式,通过所有的等式将这个图建立起来。然后再遍历所有的不等式,看这两个结点在图中是否相连,这里通过递归来检查两个结点是否相连,常规写法,注意要使用一个 HashSet 来标记已经访问过的结点,以免陷入死循环,参见代码如下:

解法一:

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        unordered_map<char, unordered_set<char>> g;
        for (auto eq : equations) {
            if (eq[1] == '!') continue;
            g[eq[0]].insert(eq[3]);
            g[eq[3]].insert(eq[0]);
        }
        for (auto eq : equations) {
            if (eq[1] == '=') continue;
            unordered_set<char> visited;
            if (!check(g, eq[0], eq[3], visited)) return false;
        }
        return true;
    }
    bool check(unordered_map<char, unordered_set<char>>& g, char cur, char target, unordered_set<char>& visited) {
        if (cur == target || g[cur].count(target)) return false;
        for (char c : g[cur]) {
            if (visited.count(c)) continue;
            visited.insert(c);
            if (!check(g, c, target, visited)) return false;
        }
        return true;
    }
};

这道题给的提示使用联合查找/并查集 Union Find,论坛上的高分解法也是清一色的 UF 做法。核心思想是初始时给每一个对象都赋上不同的标签,然后对于所有的等式,可以看作是属于同一个群组的对象,需要在 root 数组中标记一下,标记方法是两个对象分别调用 find 函数来找出祖先标签值,然后在 root 数组中再将这两个值连接起来。接下来遍历所有不等式,对不等号两端的对象分别调用 find 函数来找出祖先标签值,若相等了,则产生了矛盾了,因为这两个对象 suppose 不能属于同一个群组的,直接返回 false,参见代码如下:

解法二:

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        vector<int> root(26);
        for (int i = 0; i < 26; ++i) root[i] = i;
        for (string eq : equations) {
            if (eq[1] == '!') continue;
            root[find(root, eq[0] - 'a')] = find(root, eq[3] - 'a');
        }
        for (string eq : equations) {
            if (eq[1] == '=') continue;
            if (find(root, eq[0] - 'a') == find(root, eq[3] - 'a')) return false;
        }
        return true;
    }
    int find(vector<int>& root, int x) {
        return root[x] == x ? x : find(root, root[x]);
    }
};

讨论:find 函数的写法其实有很多种,有递归形式,也有迭代形式的,可以参见博主之前的博客 Redundant Connection II

Github 同步地址:

https://github.com/grandyang/leetcode/issues/990

类似题目:

Redundant Connection II

Friend Circles

Graph Valid Tree

参考资料:

https://leetcode.com/problems/satisfiability-of-equality-equations/

https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234474/C%2B%2B-7-lines-with-picture-union-find

https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234486/JavaC%2B%2BPython-Easy-Union-Find

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation