990. Satisfiability of Equality Equations

Posted on Edited on In

990. Satisfiability of Equality Equations

Description

Difficulty: Medium

Related Topics: Array, String, Union Find, Graph

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:

1
2
3
4
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:

1
2
3
Input: equations = ["b==a","a==b"]
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.

Hints/Notes

  • Union find
  • Handle the equation first, make the letters connected(have the same root)
  • Check the inequality next

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> parent;

    bool equationsPossible(vector<string>& equations) {
        for (int i = 0; i < 26; i++) {
            parent.push_back(i);
        }

        for (string equation : equations) {
            if (equation[1] == '=') {
                int left = equation[0] - 'a';
                int right = equation[3] - 'a';
                int rootLeft = find(left);
                int rootRight = find(right);
                if (rootLeft != rootRight) {
                    parent[rootLeft] = rootRight;
                }
            }
        }

        for (string equation : equations) {
            if (equation[1] == '!') {
                int left = equation[0] - 'a';
                int right = equation[3] - 'a';
                int rootLeft = find(left);
                int rootRight = find(right);
                if (rootLeft == rootRight) {
                    return false;
                }
            }
        }

        return true;
    }

    int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }
};