Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/399.html

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]

 

Constraints:

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

Algorithm

Need a HashSet to record the expressions that have been visited, and then call a recursive function on it.

In the recursive function, we quickly find the expression in the HashMap,

  • If it is equal to a known expression, return the result directly.
  • If not, then we need to look for it indirectly. We traverse the known conditions in the HashMap that are the same as the numerator in the analytic formula, skip the ones that have been traversed before, or add the visited array, and then call the recursive function.
    • If the return value is a positive number, it will be multiplied by the value of the current known condition and returned, similar to the case 1 above. After the multiplication, b will be eliminated.
    • If it is known that no solution is found, -1 will be returned at the end

Code

  • import java.util.*;
    
    public class Evaluate_Division {
    
        class Solution {
            public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    
                Map<String, Map<String, Double>> graph = buildGraph(equations, values);
    
                double[] result = new double[queries.size()];
    
                for (int i = 0; i < queries.size(); i++) {
                    String start = queries.get(i).get(0);
                    String end = queries.get(i).get(1);
    
                    Set<String> visited = new HashSet<>();
                    result[i] = calculate(graph, start, end, visited);
                }
    
                return result;
            }
    
            private double calculate(Map<String, Map<String, Double>> graph, String start, String end, Set<String> visited) {
    
                if (!graph.containsKey(start) || !graph.containsKey(end)) {
                    return -1.0;
                }
    
                // stop here
                if (graph.get(start).containsKey(end)) {
                    return graph.get(start).get(end);
                }
    
                if (start.equals(end)) {
                    return 1.0;
                }
    
                // start dfs
                visited.add(start); // @note: no need to visited.remove() after recursion
    
                Map<String, Double> nextSearch = graph.get(start);
                for (Map.Entry<String, Double> entry: nextSearch.entrySet()) {
    
                    String newStart = entry.getKey();
                    double factor = entry.getValue();
    
                    if (!visited.contains(newStart)) {
                        double dfsResult = calculate(graph, newStart, end, visited);
                        if (dfsResult > 0) {
                            return factor * dfsResult;
                        }
                    }
                }
    
                visited.remove(start); // restore
                return -1.0;
            }
    
            private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    
                // a => (b=>2.0)
                Map<String, Map<String, Double>> graph = new HashMap<>();
    
                for (int i = 0; i < values.length; i++) {
                    List<String> equation = equations.get(i);
                    String node1 = equation.get(0);
                    String node2 = equation.get(1);
    
                    graph.putIfAbsent(node1, new HashMap<String, Double>());
                    graph.putIfAbsent(node2, new HashMap<String, Double>());
    
                    graph.get(node1).put(node2, values[i]);
                    graph.get(node2).put(node1, 1.0 / values[i]); // possible bug, value is 0
                }
    
                return graph;
            }
    
        }
    }
    
    ############
    
    class Solution {
        private Map<String, String> p;
        private Map<String, Double> w;
    
        public double[] calcEquation(
            List<List<String>> equations, double[] values, List<List<String>> queries) {
            int n = equations.size();
            p = new HashMap<>();
            w = new HashMap<>();
            for (List<String> e : equations) {
                p.put(e.get(0), e.get(0));
                p.put(e.get(1), e.get(1));
                w.put(e.get(0), 1.0);
                w.put(e.get(1), 1.0);
            }
            for (int i = 0; i < n; ++i) {
                List<String> e = equations.get(i);
                String a = e.get(0), b = e.get(1);
                String pa = find(a), pb = find(b);
                if (Objects.equals(pa, pb)) {
                    continue;
                }
                p.put(pa, pb);
                w.put(pa, w.get(b) * values[i] / w.get(a));
            }
            int m = queries.size();
            double[] ans = new double[m];
            for (int i = 0; i < m; ++i) {
                String c = queries.get(i).get(0), d = queries.get(i).get(1);
                ans[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d))
                    ? -1.0
                    : w.get(c) / w.get(d);
            }
            return ans;
        }
    
        private String find(String x) {
            if (!Objects.equals(p.get(x), x)) {
                String origin = p.get(x);
                p.put(x, find(p.get(x)));
                w.put(x, w.get(x) * w.get(origin));
            }
            return p.get(x);
        }
    }
    
  • // OJ: https://leetcode.com/problems/evaluate-division/
    class Solution {
    private:
        unordered_map<string, unordered_map<string, double>> m;
        double dfs(string from, string to, set<string> &visited) {
            if (m[from].count(to)) return m[from][to];
            for (auto p : m[from]) {
                if (visited.count(p.first)) continue;
                visited.insert(p.first);
                double v = dfs(p.first, to, visited);
                if (v != -1) return p.second * v;
            }
            return -1;
        }
    public:
        vector<double> calcEquation(vector<vector<string>> &equations, vector<double>& values, vector<vector<string>> queries) {
            for (int i = 0; i < equations.size(); ++i) {
                auto &e = equations[i];
                m[e[0]][e[1]] = values[i];
                m[e[1]][e[0]] = 1 / values[i];
            }
            vector<double> ans;
            for (auto q : queries) {
                set<string> visited;
                auto &a = q[0], &b = q[1];
                if (!m.count(a) || !m.count(b)) ans.push_back(-1);
                else if (a == b) ans.push_back(1);
                else ans.push_back(dfs(a, b, visited));
            }
            return ans;
        }
    };
    
  • class Solution:
        def calcEquation(
            self, equations: List[List[str]], values: List[float], queries: List[List[str]]
        ) -> List[float]:
            def find(x):
                if p[x] != x:
                    origin = p[x]
                    p[x] = find(p[x])
                    w[x] *= w[origin]
                return p[x]
    
            w = defaultdict(lambda: 1)
            p = defaultdict()
            for a, b in equations:
                p[a], p[b] = a, b
            for i, v in enumerate(values):
                a, b = equations[i]
                pa, pb = find(a), find(b)
                if pa == pb:
                    continue
                p[pa] = pb
                w[pa] = w[b] * v / w[a]
            return [
                -1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d]
                for c, d in queries
            ]
    
    ############
    
    from collections import deque
    
    
    class Graph(object):
      def __init__(self):
        self.graph = {}
    
      def get(self, label):
        if label not in self.graph:
          self.graph[label] = GraphNode(label)
        return self.graph[label]
    
      def query(self, node1, node2):
        g = self.graph
        if len(node1.nbrs) == 0 or len(node2.nbrs) == 0:
          return -1.0
        if node1 == node2:
          return 1.0
        queue = deque([(node1, 1)])
        visited = set([node1.label])
        while queue:
          node, ans = queue.popleft()
          for nbr in node.nbrs:
            if nbr not in visited:
              w = node.nbrs[nbr]
              visited |= {nbr}
              nbrNode = g.get(nbr)
              if nbrNode == node2:
                return ans * w
              queue.append((nbrNode, ans * w))
    
        return -1.0
    
      def connect(self, node1, node2, div):
        node1.nbrs[node2.label] = div
        if div != 0:
          node2.nbrs[node1.label] = 1.0 / div
        else:
          node2.nbrs[node1.label] = float("inf")
    
    
    class GraphNode(object):
      def __init__(self, label):
        self.label = label
        self.nbrs = {}
    
    
    class Solution(object):
      def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        visited = {}
        g = Graph()
        ans = []
        for i in range(0, len(equations)):
          label1, label2 = equations[i]
          node1, node2 = g.get(label1), g.get(label2)
          g.connect(node1, node2, values[i])
    
        for query in queries:
          ans.append(g.query(g.get(query[0]), g.get(query[1])))
        return ans
    
    
  • func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    	p := make(map[string]string)
    	w := make(map[string]float64)
    	for _, e := range equations {
    		a, b := e[0], e[1]
    		p[a], p[b] = a, b
    		w[a], w[b] = 1.0, 1.0
    	}
    
    	var find func(x string) string
    	find = func(x string) string {
    		if p[x] != x {
    			origin := p[x]
    			p[x] = find(p[x])
    			w[x] *= w[origin]
    		}
    		return p[x]
    	}
    
    	for i, v := range values {
    		a, b := equations[i][0], equations[i][1]
    		pa, pb := find(a), find(b)
    		if pa == pb {
    			continue
    		}
    		p[pa] = pb
    		w[pa] = w[b] * v / w[a]
    	}
    	var ans []float64
    	for _, e := range queries {
    		c, d := e[0], e[1]
    		if p[c] == "" || p[d] == "" || find(c) != find(d) {
    			ans = append(ans, -1.0)
    		} else {
    			ans = append(ans, w[c]/w[d])
    		}
    	}
    	return ans
    }
    

All Problems

All Solutions