Self-explanatory Python codes


  • 0
    class Solution(object):
        def cal(self, G, visited, start, dest, weight):
            if start == dest: return weight
            visited[start] = True
            for key in G[start]:
                if not visited[key]:
                    r = self.cal(G, visited, key, dest, weight*G[start][key])
                    if r != -1: return r
            return -1.0
        
        def calcEquation(self, equations, values, queries):
            G = {}; visited = {}
            for i in xrange(len(values)):
                start = equations[i][0]
                end = equations[i][1]
                weight = values[i]
                if start not in G: G[start] = {}
                G[start][end] = weight
                if end not in G: G[end] = {}
                G[end][start] = 1/weight
                if start not in visited: visited[start] = False
                if end not in visited: visited[end] = False
            re = []
            for query in queries:
                if query[0] not in G or query[1] not in G: re.append(-1.0)
                elif query[0] in G and query[0] == query[1]: re.append(1.0)
                else: re.append(self.cal(G, dict(visited), query[0], query[1], 1))
            return re
    

Log in to reply
 

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