Skip to content

Commit e1032ec

Browse files
committed
990 added.
1 parent 5846c7f commit e1032ec

File tree

4 files changed

+127
-0
lines changed

4 files changed

+127
-0
lines changed
Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.13)
2+
project(B)
3+
4+
set(CMAKE_CXX_STANDARD 11)
5+
6+
add_executable(B main.cpp)
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/// Source : https://leetcode.com/problems/satisfiability-of-equality-equations/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-02-13
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <unordered_set>
8+
9+
using namespace std;
10+
11+
12+
/// DFS
13+
/// Time Complexity: O(26^2 * n)
14+
/// Space Complexity: O(26^2)
15+
class Solution {
16+
public:
17+
bool equationsPossible(vector<string>& equations) {
18+
19+
vector<unordered_set<int>> g(26);
20+
for(const string& e: equations)
21+
if(e[1] == '=')
22+
g[e[0] - 'a'].insert(e[3] - 'a'),
23+
g[e[3] - 'a'].insert(e[0] - 'a');
24+
25+
for(const string& e: equations)
26+
if(e[1] == '!' && isConnected(g, e[0] - 'a', e[3] - 'a'))
27+
return false;
28+
return true;
29+
}
30+
31+
private:
32+
bool isConnected(const vector<unordered_set<int>>& g, int x, int y){
33+
34+
vector<bool> visited(26, false);
35+
return dfs(g, x, y, visited);
36+
}
37+
38+
bool dfs(const vector<unordered_set<int>>& g, int s, int t, vector<bool>& visited){
39+
40+
visited[s] = true;
41+
if(s == t) return true;
42+
for(int next: g[s])
43+
if(!visited[next] && dfs(g, next, t, visited))
44+
return true;
45+
return false;
46+
}
47+
};
48+
49+
50+
int main() {
51+
52+
return 0;
53+
}
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/// Source : https://leetcode.com/problems/satisfiability-of-equality-equations/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-02-09
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Using Union-Found
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(26)
14+
class UF{
15+
16+
private:
17+
vector<int> parent;
18+
19+
public:
20+
UF(int n){
21+
for(int i = 0 ; i < n ; i ++)
22+
parent.push_back(i);
23+
}
24+
25+
int find(int p){
26+
if( p != parent[p] )
27+
parent[p] = find( parent[p] );
28+
return parent[p];
29+
}
30+
31+
bool isConnected(int p , int q){
32+
return find(p) == find(q);
33+
}
34+
35+
void unionElements(int p, int q){
36+
37+
int pRoot = find(p);
38+
int qRoot = find(q);
39+
40+
if( pRoot == qRoot )
41+
return;
42+
43+
parent[pRoot] = qRoot;
44+
}
45+
};
46+
47+
class Solution {
48+
public:
49+
bool equationsPossible(vector<string>& equations) {
50+
51+
UF uf(26);
52+
for(const string& e: equations)
53+
if(e[1] == '=')
54+
uf.unionElements(e[0] - 'a', e[3] - 'a');
55+
56+
for(const string& e: equations)
57+
if(e[1] == '!' && uf.isConnected(e[0] - 'a', e[3] - 'a'))
58+
return false;
59+
return true;
60+
}
61+
};
62+
63+
64+
int main() {
65+
66+
return 0;
67+
}

readme.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -648,4 +648,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
648648
| 987 | [Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/) | [solution](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/solution/) | [C++](0987-Vertical-Order-Traversal-of-a-Binary-Tree/cpp-0987/) | | |
649649
| 988 | [Smallest String Starting From Leaf](https://leetcode.com/problems/smallest-string-starting-from-leaf/) | [solution](https://leetcode.com/problems/smallest-string-starting-from-leaf/solution/) | [C++](0988-Smallest-String-Starting-From-Leaf/cpp-0988/) | | |
650650
| 989 | [Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/) | [solution](https://leetcode.com/problems/add-to-array-form-of-integer/solution/) | [C++](0989-Add-to-Array-Form-of-Integer/cpp-0989/) | | |
651+
| 990 | [Satisfiability of Equality Equations](https://leetcode.com/problems/satisfiability-of-equality-equations/) | [solution](https://leetcode.com/problems/satisfiability-of-equality-equations/solution/) | [C++](0990-Satisfiability-of-Equality-Equations/cpp-0990/) | | |
651652
| | | | | | |

0 commit comments

Comments
 (0)