399. Evaluate Division #

Problem #

Equations are given 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.

Example:

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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Problem Summary #

Given equations in the form A / B = k, where A and B are variables represented as strings, and k is a floating-point number. Solve the queries based on the known equations and return the calculation results. If the result does not exist, return -1.0.

Example: Given a / b = 2.0, b / c = 3.0 Queries: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? Return [6.0, 0.5, -1.0, 1.0, -1.0 ]

The input is: vector<pair<string, string» equations, vector& values, vector<pair<string, string» queries (equations, equation results, query equations), where equations.size() == values.size(), meaning the length of the equations equals the length of the equation results (the equations and results correspond one-to-one), and all result values are positive. The above describes the equations. Return a vector type.

Assume the input is always valid. You may assume there will be no division by zero during division operations, and there are no contradictory results.

Solution Approach #

Given the multiple relationships between some letter variables, ask what the multiple is between any two given letters.
This problem can be solved using DFS or Union-Find. First, let’s look at the DFS approach. Build the graph first. Each letter or letter combination can be regarded as a node, and the given equations relationships can be regarded as directed edges between two nodes. Each directed edge has a weight. Then the problem can be transformed into whether there exists a path from the starting node to the ending node. If it exists, output the cumulative product of the weights of all directed edges on this path. If this path does not exist, return -1. If the given starting point and ending point are not in the given node set, also output -1.
Now let’s look at the Union-Find approach. First perform the Union-Find union() operation on every two nodes that have a multiple relationship. For example, A/B = 2, then take B as the parent node, parents[A] = {B, 2}, parents[B] = {B, 1}, and B points to itself with value 1. There is another relationship B/C=3. Since B is already in the Union-Find set, at this time this relationship needs to be reversed and processed as C/B = 1/3, namely parents[C] = {B, 1/3}. In this way, union() all letters that have relationships together. How do we find the multiple relationship between any two letters? For example, for A/C = ?, searching in the Union-Find set, we can find parents[C] == parents[A] == B, so use parents[A]/parents[C] = 2/(1/3) = 6. Why can this be done? Because A/B = 2 and C/B = 1/3, so A/C = (A/B)/(C/B), namely parents[A]/parents[C] = 2/(1/3) = 6.

Code #


package leetcode

type stringUnionFind struct {
	parents map[string]string
	vals    map[string]float64
}

func (suf stringUnionFind) add(x string) {
	if _, ok := suf.parents[x]; ok {
		return
	}
	suf.parents[x] = x
	suf.vals[x] = 1.0
}

func (suf stringUnionFind) find(x string) string {
	p := ""
	if v, ok := suf.parents[x]; ok {
		p = v
	} else {
		p = x
	}
	if x != p {
		pp := suf.find(p)
		suf.vals[x] *= suf.vals[p]
		suf.parents[x] = pp
	}
	if v, ok := suf.parents[x]; ok {
		return v
	}
	return x
}

func (suf stringUnionFind) union(x, y string, v float64) {
	suf.add(x)
	suf.add(y)
	px, py := suf.find(x), suf.find(y)
	suf.parents[px] = py
	// x / px = vals[x]
	// x / y = v
	// From the above 2 equations, we can derive px = v * vals[y] / vals[x]
	suf.vals[px] = v * suf.vals[y] / suf.vals[x]
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	res, suf := make([]float64, len(queries)), stringUnionFind{parents: map[string]string{}, vals: map[string]float64{}}
	for i := 0; i < len(values); i++ {
		suf.union(equations[i][0], equations[i][1], values[i])
	}
	for i := 0; i < len(queries); i++ {
		x, y := queries[i][0], queries[i][1]
		if _, ok := suf.parents[x]; ok {
			if _, ok := suf.parents[y]; ok {
				if suf.find(x) == suf.find(y) {
					res[i] = suf.vals[x] / suf.vals[y]
				} else {
					res[i] = -1
				}
			} else {
				res[i] = -1
			}
		} else {
			res[i] = -1
		}
	}
	return res
}