Python 32ms DFS solution


  • 0
    A
    class Solution(object):
        def calcEquation(self, equations, values, query):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type query: List[List[str]]
            :rtype: List[float]
            """
            chain, vals = {}, {}
            for i in range(len(equations)):
                pair = equations[i]
                nomin, denom = pair[0], pair[1]
                if nomin in chain.keys():
                    chain[nomin].add((nomin, denom))
                else:
                    chain[nomin] = {(nomin, denom)}
                if denom in chain.keys():
                    chain[denom].add((denom, nomin))
                else:
                    chain[denom] = {(denom, nomin)}
                vals[(nomin, denom)], vals[(denom, nomin)] = values[i], 1.0 / values[i]
            def dfs(pair, chain, vals, marker):
                nomin, denom = pair[0], pair[1]
                if nomin not in chain.keys() or denom not in chain.keys():
                    return -1.0
                if pair in chain[nomin]:
                    return vals[pair]
                for candidate in chain[nomin]:
                    if candidate[1] != denom and candidate[1] not in marker:
                        marker.add(candidate[1])
                        res = vals[candidate] * dfs((candidate[1], denom), chain, vals, marker)
                        if res > 0:
                            return res
                        else:
                            marker.discard(candidate[1])
                return -1.0
            return [dfs((pair[0], pair[1]), chain, vals, {pair[0]}) for pair in query]
    

Log in to reply
 

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