python hashmap and bfs ( a bit awkward)

  • 0

    I thought I try a complicated method.

    I first use hashmap to store the graph. each link represent the relative value of the two node.

    Then use bfs to traverse the graph, and get the virtual value of each node.

    I use variable "group" to indicate whether they have relation or not.

    from collections import deque

    class Solution(object):
    def calcEquation(self, equations, values, query):

        if len(equations) == 0:
            return [ -1 for i in xrange(len(query))]
        dic = {}
        for i in xrange(len(equations)):
            equation = equations[i]
            v = values[i]
            e1 = equation[0]
            e2 = equation[1]
            if e1 not in dic:
                dic[e1] = []
            if e2 not in dic:
                dic[e2] = []
            if v != 0:
                dic[e2].append((e1, 1.0 / float(v)))
        res = {}
        group = 0
        for k in dic:
            if k not in res:
                res[k] = (1,group)
                q = deque([])
                while len(q) != 0:
                    cur = q.popleft()
                    for relative in dic[cur]:
                        if relative[0] not in res:
                            res[relative[0]] = (float(res[cur][0]) / float(relative[1]),group)
                group += 1
        #generate answer
        ans = []
        for q in query:
            a = q[0]
            b = q[1]
            if a in res and b in res and res[a][1] == res[b][1]:
                ans.append(float(res[a][0]) / float(res[b][0]))
        return ans


Log in to reply

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