Java Solution


  • 0
    W

    Basic idea is store both the equation and value into hashmap and using recursive to find out the answer.
    when store the equation, it should be stored the reverse equation as well so that it could be able to deal with the queries such as " a/b=2, b/c=2, a/c=? " and " a/b=2, c/b=2, a/c=? ".
    '''
    public class Solution {
    Map<String, helper> map=new HashMap<>();
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    double[] ans=new double[queries.length];
    for(int i=0;i<equations.length;i++){
    if(map.containsKey(equations[i][0])){
    map.get(equations[i][0]).str.add(equations[i][1]);
    map.get(equations[i][0]).div.add(values[i]);
    }
    else{
    map.put(equations[i][0],new helper());
    map.get(equations[i][0]).str.add(equations[i][1]);
    map.get(equations[i][0]).div.add(values[i]);
    }
    if(map.containsKey(equations[i][1])){
    map.get(equations[i][1]).str.add(equations[i][0]);
    map.get(equations[i][1]).div.add(1.0/values[i]);
    }
    else{
    map.put(equations[i][1],new helper());
    map.get(equations[i][1]).str.add(equations[i][0]);
    map.get(equations[i][1]).div.add(1.0/values[i]);
    }
    }
    for(int i=0;i<queries.length;i++){
    ans[i]=recursive(queries[i][0],queries[i][1], "");
    }
    return ans;
    }
    public double recursive(String a, String b, String prev){
    if(!map.containsKey(a)){
    return -1.0;
    }
    if(a.equals(b)){
    return 1.0;
    }
    List<String> s=map.get(a).str;
    List<Double> d=map.get(a).div;
    double ans=-1.0;
    for(int i=0;i<s.size();i++){
    if(s.get(i).equals(prev)) continue;
    if(s.get(i).equals(b)){
    return d.get(i);
    }
    double tmp=recursive(s.get(i), b, a);
    if(tmp!=-1.0){
    ans=tmp*d.get(i);
    break;
    }
    }
    return ans;
    }
    class helper{
    List<String> str;
    List<Double> div;
    helper(){
    str=new ArrayList<>();
    div=new ArrayList<>();
    }
    }
    }
    '''


Log in to reply
 

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