LeetCode 399 Evaluate Division

LeetCode

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A<sub>i</sub>, B<sub>i</sub>] and values[i] represent the equation A<sub>i</sub> / B<sub>i</sub> = values[i]. Each A<sub>i</sub> or B<sub>i</sub> is a string that represents a single variable.

You are also given some queries, where queries[j] = [C<sub>j</sub>, D<sub>j</sub>] represents the j<sup>th</sup> query where you must find the answer for C<sub>j</sub> / D<sub>j</sub> = ?.

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 <= A<sub>i</sub>.length, B<sub>i</sub>.length <= 5 values.length == equations.length
0.0 < values[i] <= 20.0 1 <= queries.length <= 20
queries[i].length == 2 1 <= C<sub>j</sub>.length, D<sub>j</sub>.length <= 5
* A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub> consist of lower case English letters and digits.

题目大意：

根据已知除法结果求其他除法表达式

解题思路：

这是G家的面试题。图问题，因为每个除法式相乘可以得到query所要的，所以属于图问题。可以用BFS来遍历图，如已知a/b = 2, b/c = 3, 需要知道a/c, 就是2 x 3，所以只要从a开始， c为BFS的target，迭代时不断相乘

解题步骤：

N/A

注意事项：

1. 核心思想： BFS来遍历图，迭代时不断相乘。无向图，因为a/c也可以c/a.
2. BFS的注意事项后两个：BFS无解时候不存在的时候返回-1
3. 两种edge cases： 若query中任意元素不在图中，返回-1(题目要求), 若元素相等，返回1

Python代码：

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
	graph = collections.defaultdict(list)
	for i, li in enumerate(equations):
		graph[li[0]].append((li[1], values[i]))
		graph[li[1]].append((li[0], 1 / values[i])) # remember it is an undirected graph
	res = []
	for query in queries:
		if query[0] not in graph or query[1] not in graph:
			res.append(-1.0)
		elif query[0] in graph and query[0] == query[1]:
			res.append(1.0)
		else:
			val = self.bfs(graph, query)
			res.append(val)
	return res

def bfs(self, graph, query):
	queue = collections.deque([(query[0], 1)])
	visited = set([queue[0]])
	while queue:
		node, parent_val = queue.popleft()
		if node == query[1]:
			return parent_val
		for neighbor, val in graph[node]:
			if neighbor in visited:
				continue
			queue.append((neighbor, parent_val * val))
			visited.add(neighbor)
	return -1 # remember

算法分析：

时间复杂度为O(（V + E) * m)，空间复杂度O(E), m为query数