0399. Evaluate Division (M)

Evaluate Division (M)

题目

You are given equations in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating-point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

The input is always valid. You may assume that evaluating the queries will result in no division by zero and 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]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= equations[i][0], equations[i][1] <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= queries[i][0], queries[i][1] <= 5
equations[i][0], equations[i][1], queries[i][0], queries[i][1] consist of lower case English letters and digits.

题意

给定一系列字符串之间的比值，求另一组字符串对的比值。

思路

DFS搜索。将所有字符串对及其倒数存入Map。对于每个需要查询的(frac{A}{B})，如果存在则直接返回，如果不存在则拆分成(frac{A}{C} imesfrac{C}{B})，递归查询(frac{C}{B})。

代码实现

Java

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] ans = new double[queries.size()];
        Map<String, Map<String, Double>> hash = new HashMap<>();
        for (int i = 0; i < values.length; i++) {
            String A = equations.get(i).get(0);
            String B = equations.get(i).get(1);
            hash.putIfAbsent(A, new HashMap<>());
            hash.get(A).put(B, values[i]);
            hash.putIfAbsent(B, new HashMap<>());
            hash.get(B).put(A, 1.0 / values[i]);
        }
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            ans[i] = dfs(query.get(0), query.get(1), hash, new HashSet<>());
        }
        return ans;
    }

    private double dfs(String A, String B, Map<String, Map<String, Double>> hash, Set<String> visited) {
        if (!hash.containsKey(A)) {
            return -1.0;
        }
        if (A == B) {
            return 1.0;
        }
        if (hash.get(A).containsKey(B)) {
            return hash.get(A).get(B);
        }
        for (String C : hash.get(A).keySet()) {
            if (!visited.contains(C)) {
                visited.add(C);
                double tmp = dfs(C, B, hash, visited);
                if (tmp > 0) {
                    return hash.get(A).get(C) * tmp;
                }
            }
        }
        return -1.0;
    }
}