Skip to content

399. Evaluate Division 👍

  • Time: $O(|\texttt{equations}| + |\texttt{equations}|q) = O(|\texttt{equations}|q)$
  • Space: $O(|\texttt{equations}| + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
 public:
  vector<double> calcEquation(vector<vector<string>>& equations,
                              vector<double>& values,
                              vector<vector<string>>& queries) {
    vector<double> ans;
    // graph[A][B] := A / B
    unordered_map<string, unordered_map<string, double>> graph;

    for (int i = 0; i < equations.size(); ++i) {
      const string& A = equations[i][0];
      const string& B = equations[i][1];
      graph[A][B] = values[i];
      graph[B][A] = 1 / values[i];
    }

    for (const vector<string>& query : queries) {
      const string& A = query[0];
      const string& C = query[1];
      if (!graph.contains(A) || !graph.contains(C))
        ans.push_back(-1);
      else
        ans.push_back(divide(graph, A, C, unordered_set<string>()));
    }

    return ans;
  }

 private:
  // Returns A / C.
  double divide(
      const unordered_map<string, unordered_map<string, double>>& graph,
      const string& A, const string& C, unordered_set<string>&& seen) {
    if (A == C)
      return 1.0;

    seen.insert(A);

    // value := A / B
    for (const auto& [B, value] : graph.at(A)) {
      if (seen.contains(B))
        continue;
      const double res = divide(graph, B, C, std::move(seen));  // B / C
      if (res > 0)                                              // valid result
        return value * res;  // A / C = (A / B) * (B / C)
    }

    return -1;  // invalid result
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
  public double[] calcEquation(List<List<String>> equations, double[] values,
                               List<List<String>> queries) {
    double[] ans = new double[queries.size()];
    // graph.get(A).get(B) := A / B
    Map<String, Map<String, Double>> graph = new HashMap<>();

    // Construct the graph.
    for (int i = 0; i < equations.size(); ++i) {
      final String A = equations.get(i).get(0);
      final String B = equations.get(i).get(1);
      graph.putIfAbsent(A, new HashMap<>());
      graph.putIfAbsent(B, new HashMap<>());
      graph.get(A).put(B, values[i]);
      graph.get(B).put(A, 1.0 / values[i]);
    }

    for (int i = 0; i < queries.size(); ++i) {
      final String A = queries.get(i).get(0);
      final String C = queries.get(i).get(1);
      if (!graph.containsKey(A) || !graph.containsKey(C))
        ans[i] = -1.0;
      else
        ans[i] = divide(graph, A, C, new HashSet<>());
    }

    return ans;
  }

  // Returns A / C.
  private double divide(Map<String, Map<String, Double>> graph, final String A, final String C,
                        Set<String> seen) {
    if (A.equals(C))
      return 1.0;

    seen.add(A);

    for (final String B : graph.get(A).keySet()) {
      if (seen.contains(B))
        continue;
      final double res = divide(graph, B, C, seen); // B / C
      if (res > 0)                                  // valid result
        return graph.get(A).get(B) * res;           // A / C = (A / B) * (B / C)
    }

    return -1.0; // invalid result
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
  def calcEquation(
      self,
      equations: list[list[str]],
      values: list[float],
      queries: list[list[str]],
  ) -> list[float]:
    ans = []
    # graph[A][B] := A / B
    graph = collections.defaultdict(dict)

    for (A, B), value in zip(equations, values):
      graph[A][B] = value
      graph[B][A] = 1 / value

    def devide(A: str, C: str, seen: set[str]) -> float:
      """Returns A / C."""
      if A == C:
        return 1.0

      seen.add(A)

      # value := A / B
      for B, value in graph[A].items():
        if B in seen:
          continue
        res = devide(B, C, seen)  # B / C
        if res > 0:  # valid result
          return value * res  # (A / B) * (B / C) = A / C

      return -1.0  # invalid result

    for A, C in queries:
      if A not in graph or C not in graph:
        ans.append(-1.0)
      else:
        ans.append(devide(A, C, set()))

    return ans