LeetCode 솔루션 분류
[5/20] 399. Evaluate Division
본문
관련자료
-
링크
댓글 1
JayShin님의 댓글
- 익명
- 작성일
# Time Complexity: O(n + e), Space Compleixty: O(n + e)
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = defaultdict(dict)
for (u, v), val in zip(equations, values):
graph[u][v] = val
graph[v][u] = 1 / val
def dfs(u, v, visited):
if (v not in graph):
return -1.0
elif (u == v):
return 1
elif (v in graph[u]):
return graph[u][v]
visited.add(u)
for c in graph[u]:
if c not in visited:
cToV = dfs(c, v, visited)
if (cToV != -1.0):
graph[u][v] = graph[u][c] * cToV
return graph[u][v]
return -1.0
return [dfs(u, v, set()) for (u, v) in queries]