# 399 Evaluate Division

input: equation, values and queries

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]

output: the answers to input queries.

Concept:

用一個Map來存每個代數符號除以不同的數的結果。

例如：

{a={b=2.0}, 
 b={a=0.5, c=3.0}, 
 c={b=0.3333333333333333}}

每讀一個query就從map裡面找，看query的被除數是否可以在map裡找到除數和相除的結果。

Implementation:

1. Main(): 呼叫buildMap先將map建好，再用for loop讀取每個query。
2. handleQueries():
3. buildMap(): 讀取所有equation，用每個equation的被除數當key輸入map，再用除數當key，value的倒數當value輸入map。

Pseudocode:

Main():
用一個map來存variable，和它所有可能的除出來的結果
例如：a/b=2.0, b/c = 3.0
a: [b:2.0]
b: [a:0.5] [c:3.0]
c: [b:0.333]
讀querie時，檢查queries[i][0]有沒有在map中，
如果有，取出key為queries[i][0]的value，看queries[i][1]有沒有在value中，
如果有，輸出，
如果沒有，如果queries[i][0]和queries[i][1]相同，輸出1.0，否則輸出-1.0。
如果沒有，輸出-1.0。

findQueries():
if(map has key numerator),
    get numerator's map
    if numerator's map has denominator,
        return value of denominator
    else
        if numerator == denominator
            return 1.0
        else
            return -1.0
else
    return -1.0

buildMap():
for each row in equations,
    Map<String, Double> submap = map.get(equations[i][0]);
    if submap is null
        submap = new HashMap<>();
        submap.put(equations[i][1],values[i]);
    map.put(equations[i][0],submap);
    Map<String, Double> submap = map.get(equations[i][1]);
    if submap is null
        submap = new HashMap<>();
        submap.put(equations[i][0],1/values[i]);
    map.put(equations[i][1],submap);

這邊寫完後發現此時handleQueries只能處理被除數和除數關係在equation裡有定義好的情況，例如a/b, b/a, b/c, c/b...等等，但是a/c沒有定義，就算不出來。而a/c其實可以從 a/b * b/c得到。

所以handleQueries不能只用querie的nominator在map中找，要看nominator的map entry中，是否有任何entry可以到達denominator。找的時候因為a找到b時會發現a也在b的map entry中，會一直循環找到停不下來，所以需要一個Set visited，紀錄已經拜訪過的nominator，就不會不斷循環拜訪了。

Code:

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String,Map<String,Double>> map = new HashMap<>();
        buildMap(equations, values, map);

        double[] ans = new double[queries.length];
        for(int i=0; i<queries.length; i++){
            Double res = findQueries(queries[i][0], queries[i][1], map,new HashSet<>());
            ans[i] = (res==null)? -1.0 : res;
        }
        return ans;
    }

    public Double findQueries(String numerator, String denominator, Map<String, Map<String, Double>> map, Set<String> visited){
        String visitedKey = numerator+":"+denominator;
        if(visited.contains(visitedKey))
            return null;
        if(!map.containsKey(numerator) || !map.containsKey(denominator))
            return null;
        if(numerator.equals(denominator))
            return 1.0;

        Map<String,Double> submap = map.get(numerator);
        visited.add(visitedKey);
        for(String key : submap.keySet()){
            Double res = findQueries(key, denominator, map, visited);
            if(res!=null){
                return res * submap.get(key);
            }
        }
        visited.remove(visitedKey);
        return null;
    }

    public void buildMap(String[][] equations, double[] values, Map<String, Map<String, Double>> map){
        for(int i=0; i<equations.length; i++){
            Map<String, Double> submap = map.get(equations[i][0]);
            if( submap == null){
                submap = new HashMap<>();
            }
            submap.put(equations[i][1],values[i]);
            map.put(equations[i][0],submap);
            submap = map.get(equations[i][1]);
            if( submap == null){
                submap = new HashMap<>();
            }
            submap.put(equations[i][0],1/values[i]);
            map.put(equations[i][1],submap);
        }
    }
}