Share my Python Simple Solution Dict + BackTracking

  • 0
    class Solution(object):
        def calcEquation(self, equations, values, queries):
            from collections import defaultdict    
            dens = defaultdict(list)
            for i, eq in enumerate(equations):
                dens[eq[0]].append((eq[1], values[i]))
                dens[eq[1]].append((eq[0], 1 / values[i]))
            def searchfrac(cur, sv, frac):
                if cur not in dens or sv not in dens or visited[cur]: return -1.0
                if cur == sv: return frac
                visited[cur] = True
                f = -1.0
                for den, val in dens[cur]:
                    f = searchfrac(den, sv, frac * val)
                    if f != -1.0: break
                visited[cur] = False
                return f
            visited = {var : False for var in dens.keys()}     
            ans = [searchfrac(q[0], q[1], 1.0) for q in queries]
            for i in range(len(ans)):
                if ans[i] == -1.0: ans[i] = searchfrac(queries[i][1], queries[i][0], 1.0)
            return ans 

Log in to reply

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