https://leetcode.com/problems/evaluate-division/public class Solution {
private Map mp;
private class Item {
public String str;
public double prop;
public Item(String s, double p) {
str = s;
prop = p;
}
} public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
mp = new HashMap(); for (int i=0; i<values.length; i++) {
String str1 = equations[i][0];
String str2 = equations[i][1];
double val = values[i]; List lt = (List)mp.remove(str2);
if (lt == null) {
lt = new ArrayList();
}
Item itm = new Item(str1, val);
lt.add(itm);
mp.put(str2, lt); lt = (List)mp.remove(str1);
if (lt == null) {
lt = new ArrayList();
}
itm = new Item(str2, 1/val);
lt.add(itm);
mp.put(str1, lt);
} double []ret = new double[queries.length];
Set st = new HashSet();
Queue qe = new LinkedList(); Iterator itr;
List lt;
Item baseItm; for (int i=0; i<queries.length; i++) {
st.clear();
qe.clear(); double dret = -1;
String str1 = queries[i][0];
String str2 = queries[i][1]; qe.offer(new Item(str2, 1));
st.add(str2); while ((baseItm = (Item)qe.poll()) != null) { lt = (List)mp.get(baseItm.str);
if (lt == null) {
continue;
} itr = lt.iterator(); while (itr.hasNext()) { Item itmm = (Item)itr.next();
if (itmm.str.equals(str1)) {
dret = itmm.prop * baseItm.prop;
break;
} if (st.contains(itmm.str)) {
continue;
}
Item newItm = new Item(itmm.str, itmm.prop*baseItm.prop);
qe.offer(newItm);
st.add(itmm.str);
} if (dret != -1) {
break;
}
} ret[i] = dret;
} return ret; }
}