Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/990.html
990. Satisfiability of Equality Equations (Medium)
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 <= 500equations[i].length == 4equations[i][0]andequations[i][3]are lowercase lettersequations[i][1]is either'='or'!'equations[i][2]is'='
Related Topics:
Union Find, Graph
Solution 1. Union Find
// OJ: https://leetcode.com/problems/satisfiability-of-equality-equations/
// Time: O(N)
// Space: O(1)
class UnionFind {
unordered_map<char, char> id;
unordered_map<char, int> rank;
public:
void connect(char a, char b) {
int x = find(a), y = find(b);
if (x == y) return;
if (rank[x] <= rank[y]) {
id[x] = y;
if (rank[x] == rank[y]) rank[y]++;
} else id[y] = x;
}
char find(char a) {
if (!id.count(a)) {
rank[a] = 1;
id[a] = a;
}
return id[a] == a ? a : (id[a] = find(id[a]));
}
};
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
UnionFind uf;
for (auto e : equations) {
if (e[1] == '=') uf.connect(e[0], e[3]);
}
for (auto e : equations) {
if (e[1] == '!' && uf.find(e[0]) == uf.find(e[3])) return false;
}
return true;
}
};
Solution 2. Union Find
// OJ: https://leetcode.com/problems/satisfiability-of-equality-equations/
// Time: O(N)
// Space: O(1)
class Solution {
int uf[26];
int find(int x) {
return uf[x] == x ? x : (uf[x] = find(uf[x]));
}
public:
bool equationsPossible(vector<string>& equations) {
for (int i = 0; i < 26; ++i) uf[i] = i;
for (auto e : equations) {
if (e[1] == '=') uf[find(e[0] - 'a')] = find(e[3] - 'a');
}
for (auto e : equations) {
if (e[1] == '!' && find(e[0] - 'a') == find(e[3] - 'a')) return false;
}
return true;
}
};
Solution 3. Graph Coloring (DFS)
// OJ: https://leetcode.com/problems/satisfiability-of-equality-equations/
// Time: O(N)
// Space: O(N)
class Solution {
vector<bool> visited = vector<bool>(26, false);
int color[26];
vector<vector<int>> adj = vector<vector<int>>(26);
void dfs(int u, int c) {
visited[u] = true;
color[u] = c;
for (auto v : adj[u]) {
if (!visited[v]) dfs(v, c);
}
}
public:
bool equationsPossible(vector<string>& equations) {
for (auto e : equations) {
if (e[1] != '=') continue;
adj[e[0] - 'a'].push_back(e[3] - 'a');
adj[e[3] - 'a'].push_back(e[0] - 'a');
}
for (int i = 0, c = 0; i < 26; ++i) {
if (!visited[i]) dfs(i, c++);
}
for (auto e : equations) {
if (e[1] == '!' && color[e[0] - 'a'] == color[e[3] - 'a']) return false;
}
return true;
}
};
-
class Solution { public boolean equationsPossible(String[] equations) { Map<Character, Set<Character>> equalMap = new HashMap<Character, Set<Character>>(); Map<Character, Set<Character>> unequalMap = new HashMap<Character, Set<Character>>(); for (String equation : equations) { char var1 = equation.charAt(0), var2 = equation.charAt(3); if (equation.charAt(1) == '=') { Set<Character> equalSet1 = equalMap.getOrDefault(var1, new HashSet<Character>()); equalSet1.add(var1); Set<Character> equalSet2 = equalMap.getOrDefault(var2, new HashSet<Character>()); equalSet2.add(var2); equalSet1.addAll(equalSet2); equalSet2.addAll(equalSet1); for (char var : equalSet1) equalMap.put(var, equalSet1); for (char var : equalSet2) equalMap.put(var, equalSet2); } else if (var1 == var2) return false; } for (String equation : equations) { if (equation.charAt(1) == '!') { char var1 = equation.charAt(0), var2 = equation.charAt(3); Set<Character> equalSet = equalMap.getOrDefault(var1, new HashSet<Character>()); if (equalSet.contains(var2)) return false; } } return true; } } ############ class Solution { private int[] p; public boolean equationsPossible(String[] equations) { p = new int[26]; for (int i = 0; i < 26; ++i) { p[i] = i; } for (String e : equations) { int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a'; if (e.charAt(1) == '=') { p[find(a)] = find(b); } } for (String e : equations) { int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a'; if (e.charAt(1) == '!' && find(a) == find(b)) { return false; } } return true; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
// OJ: https://leetcode.com/problems/satisfiability-of-equality-equations/ // Time: O(N) // Space: O(1) class UnionFind { unordered_map<char, char> id; unordered_map<char, int> rank; public: void connect(char a, char b) { int x = find(a), y = find(b); if (x == y) return; if (rank[x] <= rank[y]) { id[x] = y; if (rank[x] == rank[y]) rank[y]++; } else id[y] = x; } char find(char a) { if (!id.count(a)) { rank[a] = 1; id[a] = a; } return id[a] == a ? a : (id[a] = find(id[a])); } }; class Solution { public: bool equationsPossible(vector<string>& equations) { UnionFind uf; for (auto e : equations) { if (e[1] == '=') uf.connect(e[0], e[3]); } for (auto e : equations) { if (e[1] == '!' && uf.find(e[0]) == uf.find(e[3])) return false; } return true; } }; -
class Solution: def equationsPossible(self, equations: List[str]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(26)) for e in equations: a, b = ord(e[0]) - ord('a'), ord(e[-1]) - ord('a') if e[1] == '=': p[find(a)] = find(b) for e in equations: a, b = ord(e[0]) - ord('a'), ord(e[-1]) - ord('a') if e[1] == '!' and find(a) == find(b): return False return True ############ class Solution(object): def equationsPossible(self, equations): """ :type equations: List[str] :rtype: bool """ self.m = collections.defaultdict(list) for eq in equations: if eq[1] == '=': self.m[eq[0]].append(eq[3]) self.m[eq[3]].append(eq[0]) for eq in equations: if eq[1] == '!': if self.find(set(), eq[0], eq[3]) or self.find(set(), eq[3], eq[0]): return False return True def find(self, visited, begin, end): if begin in visited: return False visited.add(begin) if begin == end: return True for n in self.m[begin]: if self.find(visited, n, end): return True return False -
func equationsPossible(equations []string) bool { p := make([]int, 26) for i := 1; i < 26; i++ { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, e := range equations { a, b := int(e[0]-'a'), int(e[3]-'a') if e[1] == '=' { p[find(a)] = find(b) } } for _, e := range equations { a, b := int(e[0]-'a'), int(e[3]-'a') if e[1] == '!' && find(a) == find(b) { return false } } return true } -
class UnionFind { private parent: number[]; constructor() { this.parent = Array.from({ length: 26 }).map((_, i) => i); } find(index: number) { if (this.parent[index] === index) { return index; } this.parent[index] = this.find(this.parent[index]); return this.parent[index]; } union(index1: number, index2: number) { this.parent[this.find(index1)] = this.find(index2); } } function equationsPossible(equations: string[]): boolean { const uf = new UnionFind(); for (const [a, s, _, b] of equations) { if (s === '=') { const index1 = a.charCodeAt(0) - 'a'.charCodeAt(0); const index2 = b.charCodeAt(0) - 'a'.charCodeAt(0); uf.union(index1, index2); } } for (const [a, s, _, b] of equations) { if (s === '!') { const index1 = a.charCodeAt(0) - 'a'.charCodeAt(0); const index2 = b.charCodeAt(0) - 'a'.charCodeAt(0); if (uf.find(index1) === uf.find(index2)) { return false; } } } return true; }