399. Evaluate Division.md

399. Evaluate Division

---

leetcode Daily Challenge on September 27th, 2020.

leetcode Daily Challenge on January 6th, 2021.

---

Difficulty : Medium

Related Topics : Union Find、Graph

---

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.

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 87.84%, Memory Usage: 37.7 MB, less than 86.93% of Java online submissions

      double ERR = -1.0;
      public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
          Map<String, Map<String, Double>> map = new HashMap<>();
          int len = equations.size();
          for (int i = 0; i < len; i++) {
              String a = equations.get(i).get(0);
              String b = equations.get(i).get(1);
              double v = values[i];
              Map<String, Double> kv = map.getOrDefault(a, new HashMap<>());
              kv.put(b, v);
              map.put(a, kv);
              kv = map.getOrDefault(b, new HashMap<>());
              kv.put(a, 1 / v);
              map.put(b, kv);
          }
      
          len = queries.size();
          double[] res = new double[len];
          for (int i = 0; i < len; i++) {
              res[i] = dfs(queries.get(i).get(0), queries.get(i).get(1), map, new HashSet<>(), 1D);
          }
          return res;
      }
      
      double dfs(String start, String end, Map<String, Map<String, Double>> map, Set<String> checked, double t) {
          if (!map.containsKey(start)) return ERR;
      
          Map<String, Double> kv = map.get(start);
          if (kv.containsKey(end)) {
              return t * kv.get(end);
          }
      
          for (String key : kv.keySet()) {
              if (checked.contains(key)) continue;
              checked.add(key);
              double temp = dfs(key, end, map, checked, t * kv.get(key));
              if (temp != ERR) return temp;
              checked.remove(key);
          }
          return ERR;
      }
      

---

• the most votes

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 38 MB, less than 77.84% of Java online submissions

  private double dfs(double value, Map<String, Map<String, Double>> graph, String start, String end, Set<String> visited) {
      visited.add(start);
      Map<String, Double> map = graph.get(start);
      if(map.containsKey(end)) {
          return value*map.get(end);
      }
  
      for(String s : map.keySet()) {
          if(!visited.contains(s)) {
              double val = dfs(value*map.get(s), graph, s, end, visited);
              if(val != -1.0) {
                  return val;
              }
          }
  
      }
  
      return -1.0;
  }
  
  public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
      int n = queries.size();
      double[] result = new double[n];
  
      Map<String, Map<String, Double>> graph = new HashMap<>();
      for(int i = 0; i < equations.size(); i++) {
          List<String> list = equations.get(i);
          double val = values[i];
          String a = list.get(0);
          String b = list.get(1);
  
          graph.putIfAbsent(a, new HashMap<String, Double>());
          graph.putIfAbsent(b, new HashMap<String, Double>());
  
  
          graph.get(a).put(b,val);
          graph.get(b).put(a,1/val);
      }
  
      for(int i = 0; i < queries.size(); i++) {
          List<String> lt = queries.get(i);
          String a = lt.get(0);
          String b = lt.get(1);
          double cal = 1.0;
          Set<String> visited = new HashSet<>();
          if(!graph.containsKey(a) || !graph.containsKey(b)) {
              cal = -1.0;
          } else if(!a.equals(b)) {
              cal = dfs(cal, graph, a, b, visited);
          }
          result[i] = cal;
      }
  
      return result;
  }
  

---