399. Evaluate Division

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• 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<>());
            }

            map.get(equation.get(0)).add(new Node(equation.get(1), values[i]));

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

            map.get(equation.get(1)).add(new Node(equation.get(0), 1 / values[i]));
        }

        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;
        }

        visited.add(start);

        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;
    }
}