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
                    r_lis.append(-1.0)
                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
                            break
                        for k in dic_next[end]:
                            if k not in visited:
                                stack_lis.append((start, k, frac*dic_next[end][k]))
                                visited.add(k)
                    
                    if reached_goal:
                        r_lis.append(reached_goal)
                    else:
                        r_lis.append(-1.0)
                    
            return r_lis
    
    

Log in to reply
 

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