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 <= equations.length <= 500
equations[i].length == 4
equations[i][0]
andequations[i][3]
are lowercase lettersequations[i][1]
is either'='
or'!'
equations[i][2]
is'='
Solution: Union Find
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, running time: 12 ms, 7.1 MB class Solution { public: bool equationsPossible(vector<string>& equations) { iota(begin(parents_), end(parents_), 0); for (const auto& eq : equations) if (eq[1] == '=') parents_[find(eq[0])] = find(eq[3]); for (const auto& eq : equations) if (eq[1] == '!' && find(eq[0]) == find(eq[3])) return false; return true; } private: array<int, 128> parents_; int find(int x) { if (x != parents_[x]) parents_[x] = find(parents_[x]); return parents_[x]; } }; |