Depth-First Search
Breadth-First Search
Union Find
Graph
Array
String
Shortest Path
Description
You are given an array of variable pairs equations
and an array of real numbers values
, where equations[i] = [Ai , Bi ]
and values[i]
represent the equation Ai / Bi = values[i]
. Each Ai
or Bi
is a string that represents a single variable.
You are also given some queries
, where queries[j] = [Cj , Dj ]
represents the jth
query where you must find the answer for Cj / Dj = ?
.
Return the answers to all queries . If a single answer cannot be determined, return -1.0
.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.
Example 1:
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0 , b / c = 3.0
queries are: a / c = ? , b / a = ? , a / e = ? , a / a = ? , x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0
Example 2:
Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:
Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]
Constraints:
1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai .length, Bi .length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj .length, Dj .length <= 5
Ai , Bi , Cj , Dj
consist of lower case English letters and digits.
Solutions
Solution 1
Python3 Java C++ Go Rust TypeScript
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 class Solution :
def calcEquation (
self , equations : List [ List [ str ]], values : List [ float ], queries : List [ List [ str ]]
) -> List [ float ]:
def find ( x ):
if p [ x ] != x :
origin = p [ x ]
p [ x ] = find ( p [ x ])
w [ x ] *= w [ origin ]
return p [ x ]
w = defaultdict ( lambda : 1 )
p = defaultdict ()
for a , b in equations :
p [ a ], p [ b ] = a , b
for i , v in enumerate ( values ):
a , b = equations [ i ]
pa , pb = find ( a ), find ( b )
if pa == pb :
continue
p [ pa ] = pb
w [ pa ] = w [ b ] * v / w [ a ]
return [
- 1 if c not in p or d not in p or find ( c ) != find ( d ) else w [ c ] / w [ d ]
for c , d in queries
]
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
44
45 class Solution {
private Map < String , String > p ;
private Map < String , Double > w ;
public double [] calcEquation (
List < List < String >> equations , double [] values , List < List < String >> queries ) {
int n = equations . size ();
p = new HashMap <> ();
w = new HashMap <> ();
for ( List < String > e : equations ) {
p . put ( e . get ( 0 ), e . get ( 0 ));
p . put ( e . get ( 1 ), e . get ( 1 ));
w . put ( e . get ( 0 ), 1.0 );
w . put ( e . get ( 1 ), 1.0 );
}
for ( int i = 0 ; i < n ; ++ i ) {
List < String > e = equations . get ( i );
String a = e . get ( 0 ), b = e . get ( 1 );
String pa = find ( a ), pb = find ( b );
if ( Objects . equals ( pa , pb )) {
continue ;
}
p . put ( pa , pb );
w . put ( pa , w . get ( b ) * values [ i ] / w . get ( a ));
}
int m = queries . size ();
double [] ans = new double [ m ] ;
for ( int i = 0 ; i < m ; ++ i ) {
String c = queries . get ( i ). get ( 0 ), d = queries . get ( i ). get ( 1 );
ans [ i ] = ! p . containsKey ( c ) || ! p . containsKey ( d ) || ! Objects . equals ( find ( c ), find ( d ))
? - 1.0
: w . get ( c ) / w . get ( d );
}
return ans ;
}
private String find ( String x ) {
if ( ! Objects . equals ( p . get ( x ), x )) {
String origin = p . get ( x );
p . put ( x , find ( p . get ( x )));
w . put ( x , w . get ( x ) * w . get ( origin ));
}
return p . get ( 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
27
28
29
30
31
32
33
34
35
36
37
38
39 class Solution {
public :
unordered_map < string , string > p ;
unordered_map < string , double > w ;
vector < double > calcEquation ( vector < vector < string >>& equations , vector < double >& values , vector < vector < string >>& queries ) {
int n = equations . size ();
for ( auto e : equations ) {
p [ e [ 0 ]] = e [ 0 ];
p [ e [ 1 ]] = e [ 1 ];
w [ e [ 0 ]] = 1.0 ;
w [ e [ 1 ]] = 1.0 ;
}
for ( int i = 0 ; i < n ; ++ i ) {
vector < string > e = equations [ i ];
string a = e [ 0 ], b = e [ 1 ];
string pa = find ( a ), pb = find ( b );
if ( pa == pb ) continue ;
p [ pa ] = pb ;
w [ pa ] = w [ b ] * values [ i ] / w [ a ];
}
int m = queries . size ();
vector < double > ans ( m );
for ( int i = 0 ; i < m ; ++ i ) {
string c = queries [ i ][ 0 ], d = queries [ i ][ 1 ];
ans [ i ] = p . find ( c ) == p . end () || p . find ( d ) == p . end () || find ( c ) != find ( d ) ? -1.0 : w [ c ] / w [ d ];
}
return ans ;
}
string find ( string x ) {
if ( p [ x ] != x ) {
string origin = p [ x ];
p [ x ] = find ( p [ x ]);
w [ x ] *= w [ origin ];
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39 func calcEquation ( equations [][] string , values [] float64 , queries [][] string ) [] float64 {
p := make ( map [ string ] string )
w := make ( map [ string ] float64 )
for _ , e := range equations {
a , b := e [ 0 ], e [ 1 ]
p [ a ], p [ b ] = a , b
w [ a ], w [ b ] = 1.0 , 1.0
}
var find func ( x string ) string
find = func ( x string ) string {
if p [ x ] != x {
origin := p [ x ]
p [ x ] = find ( p [ x ])
w [ x ] *= w [ origin ]
}
return p [ x ]
}
for i , v := range values {
a , b := equations [ i ][ 0 ], equations [ i ][ 1 ]
pa , pb := find ( a ), find ( b )
if pa == pb {
continue
}
p [ pa ] = pb
w [ pa ] = w [ b ] * v / w [ a ]
}
var ans [] float64
for _ , e := range queries {
c , d := e [ 0 ], e [ 1 ]
if p [ c ] == "" || p [ d ] == "" || find ( c ) != find ( d ) {
ans = append ( ans , - 1.0 )
} else {
ans = append ( ans , w [ c ] / w [ d ])
}
}
return ans
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 use std :: collections :: HashMap ;
#[derive(Debug)]
pub struct DSUNode {
parent : String ,
weight : f64 ,
}
pub struct DisjointSetUnion {
nodes : HashMap < String , DSUNode > ,
}
impl DisjointSetUnion {
pub fn new ( equations : & Vec < Vec < String >> ) -> DisjointSetUnion {
let mut nodes = HashMap :: new ();
for equation in equations . iter () {
for iter in equation . iter () {
nodes . insert (
iter . clone (),
DSUNode {
parent : iter . clone (),
weight : 1.0 ,
},
);
}
}
DisjointSetUnion { nodes }
}
pub fn find ( & mut self , v : & String ) -> String {
let origin = self . nodes [ v ]. parent . clone ();
if origin == * v {
return origin ;
}
let root = self . find ( & origin );
self . nodes . get_mut ( v ). unwrap (). parent = root . clone ();
self . nodes . get_mut ( v ). unwrap (). weight *= self . nodes [ & origin ]. weight ;
root
}
pub fn union ( & mut self , a : & String , b : & String , v : f64 ) {
let pa = self . find ( a );
let pb = self . find ( b );
if pa == pb {
return ;
}
let ( wa , wb ) = ( self . nodes [ a ]. weight , self . nodes [ b ]. weight );
self . nodes . get_mut ( & pa ). unwrap (). parent = pb ;
self . nodes . get_mut ( & pa ). unwrap (). weight = ( wb * v ) / wa ;
}
pub fn exist ( & mut self , k : & String ) -> bool {
self . nodes . contains_key ( k )
}
pub fn calc_value ( & mut self , a : & String , b : & String ) -> f64 {
if ! self . exist ( a ) || ! self . exist ( b ) || self . find ( a ) != self . find ( b ) {
- 1.0
} else {
let wa = self . nodes [ a ]. weight ;
let wb = self . nodes [ b ]. weight ;
wa / wb
}
}
}
impl Solution {
pub fn calc_equation (
equations : Vec < Vec < String >> ,
values : Vec < f64 > ,
queries : Vec < Vec < String >> ,
) -> Vec < f64 > {
let mut dsu = DisjointSetUnion :: new ( & equations );
for ( i , & v ) in values . iter (). enumerate () {
let ( a , b ) = ( & equations [ i ][ 0 ], & equations [ i ][ 1 ]);
dsu . union ( a , b , v );
}
let mut ans = vec! [];
for querie in queries {
let ( c , d ) = ( & querie [ 0 ], & querie [ 1 ]);
ans . push ( dsu . calc_value ( c , d ));
}
ans
}
}
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 function calcEquation ( equations : string [][], values : number [], queries : string [][]) : number [] {
const g : Record < string , [ string , number ][] > = {};
const ans = Array . from ({ length : queries.length }, () => - 1 );
for ( let i = 0 ; i < equations . length ; i ++ ) {
const [ a , b ] = equations [ i ];
( g [ a ] ??= []). push ([ b , values [ i ]]);
( g [ b ] ??= []). push ([ a , 1 / values [ i ]]);
}
for ( let i = 0 ; i < queries . length ; i ++ ) {
const [ c , d ] = queries [ i ];
const vis = new Set < string > ();
const q : [ string , number ][] = [[ c , 1 ]];
if ( ! g [ c ] || ! g [ d ]) continue ;
if ( c === d ) {
ans [ i ] = 1 ;
continue ;
}
for ( const [ current , v ] of q ) {
if ( vis . has ( current )) continue ;
vis . add ( current );
for ( const [ intermediate , multiplier ] of g [ current ]) {
if ( vis . has ( intermediate )) continue ;
if ( intermediate === d ) {
ans [ i ] = v * multiplier ;
break ;
}
q . push ([ intermediate , v * multiplier ]);
}
if ( ans [ i ] !== - 1 ) break ;
}
}
return ans ;
}