题目

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:

  1. Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
  2. Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
  3. Explanation: 
  4. Given: a / b = 2.0, b / c = 3.0
  5. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
  6. return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

  1. Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
  2. Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

  1. Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
  2. 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。对于每个需要查询的0399. Evaluate Division (M) - 图1，如果存在则直接返回，如果不存在则拆分成0399. Evaluate Division (M) - 图2，递归查询0399. Evaluate Division (M) - 图3。

代码实现

Java

  1. class Solution {
  2.     public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
  3.         double[] ans = new double[queries.size()];
  4.         Map<String, Map<String, Double>> hash = new HashMap<>();
  5.         for (int i = 0; i < values.length; i++) {
  6.             String A = equations.get(i).get(0);
  7.             String B = equations.get(i).get(1);
  8.             hash.putIfAbsent(A, new HashMap<>());
  9.             hash.get(A).put(B, values[i]);
  10.             hash.putIfAbsent(B, new HashMap<>());
  11.             hash.get(B).put(A, 1.0 / values[i]);
  12.         }
  13.         for (int i = 0; i < queries.size(); i++) {
  14.             List<String> query = queries.get(i);
  15.             ans[i] = dfs(query.get(0), query.get(1), hash, new HashSet<>());
  16.         }
  17.         return ans;
  18.     }
  20.     private double dfs(String A, String B, Map<String, Map<String, Double>> hash, Set<String> visited) {
  21.         if (!hash.containsKey(A)) {
  22.             return -1.0;
  23.         }
  24.         if (A == B) {
  25.             return 1.0;
  26.         }
  27.         if (hash.get(A).containsKey(B)) {
  28.             return hash.get(A).get(B);
  29.         }
  30.         for (String C : hash.get(A).keySet()) {
  31.             if (!visited.contains(C)) {
  32.                 visited.add(C);
  33.                 double tmp = dfs(C, B, hash, visited);
  34.                 if (tmp > 0) {
  35.                     return hash.get(A).get(C) * tmp;
  36.                 }
  37.             }
  38.         }
  39.         return -1.0;
  40.     }
  41. }