simple python DFS solution using defaultdict


  • 0
    I
    class Solution(object):
        def calc_query_dfs(self, adj_list, visited, curr_var, dest_var, curr_val):
            if curr_var == dest_var:
                return curr_val
                
            visited.add(curr_var)
            for next_var, cost in adj_list[curr_var]:
                if next_var not in visited:
                    query_res = self.calc_query_dfs(adj_list, visited, next_var, dest_var, curr_val*cost)
                    if query_res != float(-1):
                        return query_res
                        
            return float(-1)
        
        def calcEquation(self, equations, values, queries):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type queries: List[List[str]]
            :rtype: List[float]
            """
            if not equations or not values or not queries:
                return []
                
            adj_list = defaultdict(list)
            for i, eqn in enumerate(equations):
                adj_list[eqn[0]].append((eqn[1], values[i]))
                adj_list[eqn[1]].append((eqn[0], 1.0/values[i]))
                
            result = [0]*len(queries)
            for i, query in enumerate(queries):
                if query[0] not in adj_list:
                    result[i] = float(-1)
                else:
                    visited = set()
                    result[i] = self.calc_query_dfs(adj_list, visited, query[0], query[1], 1.0)
                
            return result

Log in to reply
 

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