Untitled

mail@pastecode.io avatar
unknown
java
25 days ago
2.0 kB
3
Indexable
Never
class Solution {
    public double[] calcEquation(
        List<List<String>> equations, double[] values, List<List<String>> queries
    ) {
        Map<String, Map<String, Double>> varToDestToQuotient = new HashMap<>();
        for(int i = 0; i < equations.size(); i++) {
            String varA = equations.get(i).get(0);
            String varB = equations.get(i).get(1);
            double quotient = values[i];

            varToDestToQuotient.putIfAbsent(varA, new HashMap<>());
            varToDestToQuotient.putIfAbsent(varB, new HashMap<>());
            varToDestToQuotient.get(varA).put(varB, quotient);
            varToDestToQuotient.get(varB).put(varA, 1 / quotient);
        }

        double [] answer = new double[queries.size()];
        for(int i = 0; i < queries.size(); i++) {
            String queryVarA = queries.get(i).get(0);
            String queryVarB = queries.get(i).get(1);
            answer[i] = compute(
                queryVarA, queryVarB, varToDestToQuotient,
                new HashSet<>(), 1
            );
        }
        return answer;
    }

    private double compute(
        String queryVarA, String queryVarB, 
        Map<String, Map<String, Double>> varToDestToQuotient,
        Set<String> seen, double productSoFar
    ) {
        if(!varToDestToQuotient.containsKey(queryVarA)) {
            return -1;
        }
        if(queryVarA.equals(queryVarB)) {
            return productSoFar;
        }
        seen.add(queryVarA);
        for(Map.Entry<String, Double> entry : varToDestToQuotient.get(queryVarA).entrySet()) {
            if(seen.contains(entry.getKey())) {
                continue;
            }
            double compute = compute(
                entry.getKey(), queryVarB, varToDestToQuotient, seen, 
                productSoFar * entry.getValue()
            );
            if(compute != -1) {
                return compute;
            }
        }
        return -1;
    }
}
Leave a Comment