# Esay understand Java solution, 3ms

• ``````    public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
double[] result = new double[query.length];
// filter unexpected words
// 过滤掉没有遇见过的字符
Set<String> words = new HashSet<>();
for (String[] strs : equations) {
}
for (int i = 0; i < query.length; ++i) {
String[] keys = query[i];
if (!words.contains(keys[0]) || !words.contains(keys[1])) result[i] = -1.0d;
else {
Stack<Integer> stack = new Stack<>();
result[i] = helper(equations, values, keys, stack);
}
}
return result;
}

public double helper(String[][] equations, double[] values, String[] keys, Stack<Integer> stack) {
// 直接查找，key的顺序有正反
// look up equations directly
for (int i = 0; i < equations.length; ++i) {
if (equations[i][0].equals(keys[0]) && equations[i][1].equals(keys[1])) return values[i];
if (equations[i][0].equals(keys[1]) && equations[i][1].equals(keys[0])) return 1 / values[i];
}
// lookup equations by other equations
// 间接查找，key的顺序也有正反
for (int i = 0; i < equations.length; ++i) {
if (!stack.contains(i) && keys[0].equals(equations[i][0])) {
stack.push(i);
double temp = values[i] * helper(equations, values, new String[]{equations[i][1], keys[1]}, stack);
if (temp > 0) return temp;
else stack.pop();
}
if (!stack.contains(i) && keys[0].equals(equations[i][1])) {
stack.push(i);
double temp = helper(equations, values, new String[]{equations[i][0], keys[1]}, stack) / values[i];
if (temp > 0) return temp;
else stack.pop();
}
}
// 查不到，返回-1
return -1.0d;
}
``````

update:

Thanks for @jason88628 remind me. change from stack to set will be better.

update:

Another way for this problem, but it need more memory and more time to build a whole map of equations.

It's efficient when there is a large set of queries.

``````public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
// use table save string to integer
Map<String, Integer> table = new HashMap<>();
int len = 0;
for (String[] strings : equations)
for (String string : strings)
if (!table.containsKey(string)) table.put(string, len++);

// init map by direct equation
double[][] map = new double[len][len];
for (int i = 0; i < len; ++i)
for (int j = 0; j < len; ++j)
map[i][j] = (i == j ? 1.0d : -1.0d);
for (int i = 0; i < equations.length; ++i) {
String[] keys = equations[i];
int row = table.get(keys[0]);
int col = table.get(keys[1]);
map[row][col] = values[i];
map[col][row] = 1 / values[i];
}

// floyd-warshall like algorithm
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
for (int k = 0; k < len; ++k) {
if (map[j][i] >= 0d && map[i][k] >= 0d) map[j][k] = map[j][i] * map[i][k];
}
}
}

// query now
double[] result = new double[query.length];
for (int i = 0; i < query.length; ++i) {
String[] keys = query[i];
Integer row = table.get(keys[0]);
Integer col = table.get(keys[1]);
if (row == null || col == null) result[i] = -1.0d;
else result[i] = map[row][col];
}
return result;
}
``````

update:
A better way with union-find alogrithm. It takes less memory and time than the above one. But it's hard to understand.

You can replace class `Node` with two arrays. In that way, it will be more efficient.

``````public double[] calcEquation(String[][] equations, double[] values, String[][] query) {

// map string to integer
Map<String, Integer> mIdTable = new HashMap<>();
int len = 0;
for (String[] words : equations)
for (String word : words)
if (!mIdTable.containsKey(word)) mIdTable.put(word, len++);

// init parent index and value
Node[] nodes = new Node[len];
for (int i = 0; i < len; ++i) nodes[i] = new Node(i);

// union, you can take an example as follows
// (a/b=3)->(c/d=6)->(b/d=12)
for (int i = 0; i < equations.length; ++i) {
String[] keys = equations[i];
int k1 = mIdTable.get(keys[0]);
int k2 = mIdTable.get(keys[1]);
nodes[groupHead2].value = nodes[k1].value * values[i] / nodes[k2].value;
}

// query now
double[] result = new double[query.length];
for (int i = 0; i < query.length; ++i) {
Integer k1 = mIdTable.get(query[i][0]);
Integer k2 = mIdTable.get(query[i][1]);
if (k1 == null || k2 == null) result[i] = -1d;
else {
else result[i] = nodes[k2].value / nodes[k1].value;
}
}
return result;
}

public int find(Node[] nodes, int k) {
int p = k;
while (nodes[p].parent != p) {
p = nodes[p].parent;
// compress
nodes[k].value *= nodes[p].value;
}
// compress
nodes[k].parent = p;
return p;
}

private static class Node {
int    parent;
double value;

public Node(int index) {
this.parent = index;
this.value = 1d;
}
}
``````

• @yuxiaofei2016
Is stack contains o(n)? How about change stack to set?

• @jason88628 Yes, you are right.

• shouldn't we return -1.0 if any of the word is missing? (like a/e). So I think
` if (!words.contains(keys[0]) && !words.contains(keys[1])) ` should be
` if (!words.contains(keys[0]) || !words.contains(keys[1])) `

• @rhasan_82 Yes, my mistake. fix it

• @yuxiaofei2016 For each call of helper, you are going to iterate the whole equations? How could this be accepted, and 3ms? Need more TCs and more queries per setting!!!

• This post is deleted!

• @iambright Yes, my way is easy for understand. It's not efficient in the TestCase with large set of equations and queries.

• This post is deleted!

• This post is deleted!

• Implementing the traditional Union-Find in a new way is very impressive.

• The second method is wrong when the some values are negative numbers. I think it could pass because of the test case.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.