python solution without graph search, beat 98%


  • 1
    C

    My code does not use graph search. Instead, my idea is simple, for a/b=k1, b/c=k2, I build a map where b = 1, a = b*k1, c = b/k2 ...

        def calcEquation(self, equations, values, queries):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type queries: List[List[str]]
            :rtype: List[float]
            """
            assert len(equations) > 0
            graphs = []
            remaining = range(len(equations))
            m = {}
            
            while len(remaining) > 0:
                next = set()
                for i in remaining:
                    x, y = equations[i]
                    if len(m) == 0:
                        m[y] = 1.0
                    if x in m:
                        assert y not in m
                        m[y] = m[x]/values[i]
                    elif y in m:
                        assert x not in m
                        m[x] = m[y]*values[i]
                    else:
                        next.add(i)
                if len(next) == len(remaining):
                    graphs.append(m)
                    m = {}
                remaining = next
            else:
                graphs.append(m)
            
            result = []
            for q in queries:
                x, y = q
                for m in graphs:
                    if x in m and y in m:
                        result.append(m[x]/m[y])
                        break
                else:
                    result.append(-1.0)
            return result
    

Log in to reply
 

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