399. Evaluate Division

問題内容

• equations: 文字列のペアの配列。各ペア [Ai, Bi] は、変数 Ai と Bi を表す
• values: 実数の配列。values[i] は、equations[i] に対応する Ai / Bi の値を示す。つまり、Ai / Bi = values[i]
• queries: 文字列のペアの配列。各ペア [Cj, Dj] は、Cj / Dj の値を求める必要があるクエリを表す
• 求められているのは、すべてのクエリに対する答えの配列。もし、あるクエリの答えを決定できない場合は、-1.0 を返す

解答例

sample

class Solution:
    def calcEquation(self, eq: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def dfs(node,value):
            nonlocal ans

            visited.add(node)
            if node==dst:
                ans=value
                return

            for nbr,wt in graph[node]:
                if nbr not in visited:
                    dfs(nbr,value*wt)

        #
        graph=defaultdict(list)
        n=len(values)
        # graph
        for i in range(n):
            graph[eq[i][0]].append((eq[i][1],values[i]))
            graph[eq[i][1]].append((eq[i][0],1/values[i]))
        
        result=[]
        for src,dst in queries:
            if src not in graph or dst not in graph:
                result.append(-1)
                continue
                
            visited=set()
            ans=-1
            dfs(src,1)
            
            result.append(ans)
        return result

ポイント

• 変数間の関係を有効グラフとしてとらえる
• 各変数をグラフのノードとしている
• グラフの開始点から目的のノードまで途中の係数を積算していくと求める数値になる
• 関数dfsはその積算処理を定義している
• それ以外のforループではノードの定義やクエリ内走査を行っている