• ㊗️
• 大家
• offer
• 多多！

## Problem

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.

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 ]


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]


## Code

class Solution {
class Node{
String num;
double val;
Node(String num, double val){
this.num = num;
this.val = val;
}
}

HashMap<String, List<Node>> map = new HashMap<>();

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
// a : [b, 2]
// b : [a, 0.5], [c, 3]
// c : [b, 1/3]
for(int i = 0; i < equations.size(); i++){
List<String> equation = equations.get(i);
if(!map.containsKey(equation.get(0))){
map.put(equation.get(0), new ArrayList<>());
}

if(!map.containsKey(equation.get(1))){
map.put(equation.get(1), new ArrayList<>());
}

}

double[] res = new double[queries.size()];
for(int i = 0; i < res.length; i++){
String num1 = queries.get(i).get(0);
String num2 = queries.get(i).get(1);
res[i] = dfs(num1, num2, 1, new HashSet<>());
}

return res;
}

private double dfs(String start, String end, double value, HashSet<String> visited){
if(!map.containsKey(start)){
return -1;
}

if(visited.contains(start)){
return -1;
}

if(start.equals(end)){
return value;
}

for(Node next : map.get(start)){
double sub = dfs(next.num, end, value * next.val, visited);
if(sub != -1.0){
return sub;
}
}

visited.remove(start);

return -1;
}
}