Python / DFS / Iterative / 85.01%

  • 0
    from collections import defaultdict
    # from fractions import Fraction
    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]
            dic_next = collections.defaultdict(dict)
            for i in range(len(values)):
                lis = equations[i]
                dic_next[lis[0]][lis[1]] = values[i]
                dic_next[lis[1]][lis[0]] = 1.0/values[i]
            r_lis = []
            for q_lis in queries:
                if (q_lis[0] not in dic_next) or (q_lis[1] not in dic_next): # if not even find the element
                else:  # DFS search
                    begin, goal =  q_lis[0], q_lis[1]
                    stack_lis = [(begin, begin, 1.0)]
                    visited, reached_goal = set([begin]), None
                    while stack_lis:
                        start, end, frac = stack_lis.pop()
                        if end==goal:
                            reached_goal = frac
                        for k in dic_next[end]:
                            if k not in visited:
                                stack_lis.append((start, k, frac*dic_next[end][k]))
                    if reached_goal:
            return r_lis

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.