399.Evaluate Division

1-将除法关系转换成图的搜素

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Map<String, Double>> map = new HashMap<>();
        //generate graph;
        for(int i = 0; i < equations.length; i++){
            String[] num = equations[i];
            insertPair(map, num[0], num[1], values[i]);
            insertPair(map, num[1], num[0], 1.0 / values[i]);
        }

        double[] ans = new double[queries.length];
        for(int i = 0; i < queries.length; i++){
            String[] num = queries[i];
            Double res = doQuery(num[0], num[1], map, new HashSet<>());
            if(res == null)
                ans[i] = -1.0;
            else
                ans[i] = res;
        }
        return ans;   
    }

    public void insertPair(Map<String, Map<String, Double>> map, String num0, String num1, double value){
        Map<String, Double> tmpMap = map.getOrDefault(num0, new HashMap<>());
        tmpMap.put(num1, value);
        map.put(num0, tmpMap);
        return;
    }

    public Double doQuery(String num0, String num1, Map<String, Map<String, Double>> map, Set<String> visited){
        if(visited.contains(num0)){
            return null;
        }
        if(!map.containsKey(num0) || !map.containsKey(num1))
            return null;
        if(num0.equals(num1))
            return 1.0;
        visited.add(num0);
        Map<String, Double> tmpMap = map.get(num0);
        for(String key : tmpMap.keySet()){
            Double res = doQuery(key, num1, map, visited);
            if(res != null)
                return res * tmpMap.get(key);
        }
        visited.remove(num0);
        return null;
    }
}