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]
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0