399. Evaluate Division

Equations are given in the formatA / B = k, whereAandBare variables represented as strings, andkis a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0.

Example:
Givena / b = 2.0, b / c = 3.0.
queries are:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return[6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is:vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<double>.

According to the example above:

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

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Analysis:

DFS graph traversal. Think of consecutive division operation as traversing a graph. equations defines graph edges, and it is bi-directional graph since a/b = 2.0 means b/a = 0.5.

When traverse make sure to record VISITED nodes, otherwise it went into infinite loop as this is an bi-directional graph.

Complexity:

Time: O(N) - basically each query is a graph searching process.

Space: O(N^2) - need a map to store nodes verses a list of nodes(potentially every other node that exists)

Code:

public class Solution {

    public class DestNode{
        String dest;
        double dis;
        public DestNode(String nodeName, double distance){
            dest = nodeName;
            dis = distance;
        }
    }

    private Map<String, List<DestNode>> map;
    private Set<String> nodes;
    private Set<String> visited;

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if(queries == null || queries.length == 0){
            return new double[0];
        }
        double[] returnArr = new double[queries.length];
        Arrays.fill(returnArr, -1.0);

        if(equations == null || values == null || equations.length == 0 || values.length == 0){
            return returnArr;
        }

        map = new HashMap<String, List<DestNode>>();
        nodes = new HashSet<String>();

        for(int i = 0; i < equations.length; i++){
            String origin = equations[i][0];
            String dest = equations[i][1];

            if(map.get(origin) == null)
            {
                map.put(origin, new LinkedList<DestNode>());
            }
            List<DestNode> destListOne = map.get(origin);
            destListOne.add(new DestNode(dest, values[i]));

            if(map.get(dest) == null)
            {
                map.put(dest, new LinkedList<DestNode>());
            }
            List<DestNode> destListTwo = map.get(dest);
            destListTwo.add(new DestNode(origin, 1/values[i]));
            nodes.add(origin);
            nodes.add(dest);
        }

        for(int i = 0; i< queries.length; i++){
            String origin = queries[i][0];
            String dest = queries[i][1];
            if(nodes.contains(origin) && nodes.contains(dest)){
                visited = new HashSet<String>();
                returnArr[i] = findAnswer(origin, dest);
            }
        }
        return returnArr;
    }

    private double findAnswer(String start, String dest){
        if(start.equals(dest)){
            return 1.0;
        }
        return dfs(start, dest, 1.0);
    }

    private double dfs(String start, String dest, double value){
        if(visited.contains(start))
        {
            return -1.0;
        }
        List<DestNode> list = map.get(start);
        visited.add(start);
        for(DestNode itr : list){
            if(itr.dest.equals(dest))
            {
                return value * itr.dis;
            }
            double returnValue = dfs(itr.dest, dest, value * itr.dis);
            if(returnValue != -1.0){
                return returnValue;
            }
        }
        return -1.0;
    }
}