Union Find
Graph
Array
String
Description
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:
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:
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.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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
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 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 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
vector < int > p ;
bool equationsPossible ( vector < string >& equations ) {
p . resize ( 26 );
for ( int i = 0 ; i < 26 ; ++ i ) p [ i ] = i ;
for ( auto & e : equations ) {
int a = e [ 0 ] - 'a' , b = e [ 3 ] - 'a' ;
if ( e [ 1 ] == '=' ) p [ find ( a )] = find ( b );
}
for ( auto & e : equations ) {
int a = e [ 0 ] - 'a' , b = e [ 3 ] - 'a' ;
if ( e [ 1 ] == '!' && find ( a ) == find ( b )) return false ;
}
return true ;
}
int find ( int x ) {
if ( p [ x ] != x ) p [ x ] = find ( p [ x ]);
return p [ x ];
}
};
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 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
}
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 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 ;
}
GitHub