399. Evaluate Division

DFS

see in DFS

class Solution {
    class Data {
        String node;
        double value;
        Data(String node, double value) {
            this.node = node;
            this.value = value;
        }
    }
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, List<Data>> graph = buildGraph(equations, values);
        
        double[] result = new double[queries.size()];
        for (int i = 0 ; i < queries.size(); i++) {
            List<String> querie = queries.get(i);
            String start = querie.get(0);
            String end = querie.get(1);
            
            Set<String> visited = new HashSet<>();
            visited.add(start);
            
            result[i] = dfs(graph, start, end, visited);
        }
        return result;
    }
    private double dfs(Map<String, List<Data>> graph, String start, String end, Set<String> visited) {
        if (graph.get(start) == null || graph.get(end) == null) { // terminal condition
            return -1;
        }
        
        // terminal condition, at last to == end, so return 1, then bottom up to cal result 1*...value*value...
        if (start.equals(end)) { 
            return 1;
        }
        for (Data child : graph.get(start)) {
            String to = child.node;
            double value = child.value;
            if (visited.contains(to)) {
                continue;
            }
            visited.add(to);
            double temp = dfs(graph, to, end, visited);
            visited.remove(to);
                        
            if (temp != -1) {
                return temp*value;
            }
        }
        return -1;
    }

    private Map<String, List<Data>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, List<Data>> map = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String from = equation.get(0);
            String to = equation.get(1);
            map.putIfAbsent(from, new ArrayList<>());
            map.get(from).add(new Data(to, values[i]));
            
            map.putIfAbsent(to, new ArrayList<>());
            map.get(to).add(new Data(from, 1.0/values[i]));
        }
        return map;
    }
}


/*
Given: a / 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 ]
query c/d


a = 2b
b = 3c

  2   3
a - b - c 

a/c = 6
b/a = 1/2
a/e = -1  (can't find one of them in graph, return -1)
a/a = 1 (can find in graph)
x/x = -1  (can't find one of them in graph, return -1)


If a single answer cannot be determined, return -1.0.
ex: a/e


a/b = 1.5
b/c = 2.5 => b = 2.5c => bc = 2.5c/d = 5 => c/d = 2
bc/cd = 5

 1.5  2.5 2
a - b - c - d

a/c = 1.5*2.5 = 
c/b = 1/2.5
bc/cd = b/d = 5
cd/bc = d/b = 1/5


*/

BFS

T: O(q*n), q: queries times, n: graph nodes number

S: O(n)

class Solution {
    class Data {
        String node;
        double value;
        Data(String node, double value) {
            this.node = node;
            this.value = value;
        }
    }
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, List<Data>> graph = buildGraph(equations, values);
        
        double[] result = new double[queries.size()];
        for (int i = 0 ; i < queries.size(); i++) {
            List<String> querie = queries.get(i);
            String start = querie.get(0);
            String end = querie.get(1);
            
            //System.out.println("query -> start:" + start + ",end:" + end);
            result[i] = bfs(graph, start, end);
        }
        return result;
    }
    
    private double bfs(Map<String, List<Data>> graph, String start, String end) {
        
        // eliminate duplicate
        
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            return -1.0;
        }
        if (start.equals(end)) {
            return 1.0;
        }
        Queue<Data> queue = new LinkedList<>();
        queue.offer(new Data(start, 1.0));
        Set<String> visited = new HashSet<>();
        visited.add(start);
        
        while (!queue.isEmpty()) {
            Data cur = queue.poll();
            String from = cur.node;
            double fromValue = cur.value;

            for (Data child : graph.get(from)) {
                String to = child.node;
                double value = child.value;
                if (visited.contains(to)) {
                    continue;
                }
                
                //System.out.println("cur:" + cur + ",to:" + to + ",value:" + value);
                double result = fromValue*value;
                queue.offer(new Data(to, result));
                visited.add(to);
                if (end.equals(to)) {
                    //System.out.println("cur:" + cur + ", to:" + to + ",end:" + end);
                    return result;
                }
            }
        }
        return -1.0;
    }
    private Map<String, List<Data>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, List<Data>> map = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String from = equation.get(0);
            String to = equation.get(1);
            map.putIfAbsent(from, new ArrayList<>());
            map.get(from).add(new Data(to, values[i]));
            
            map.putIfAbsent(to, new ArrayList<>());
            map.get(to).add(new Data(from, 1.0/values[i]));
        }
        return map;
    }
}


/*
Given: a / 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 ]
query c/d


a = 2b
b = 3c

  2   3
a - b - c 

a/c = 6
b/a = 1/2
a/e = -1  (can't find one of them in graph, return -1)
a/a = 1 (can find in graph)
x/x = -1  (can't find one of them in graph, return -1)


If a single answer cannot be determined, return -1.0.
ex: a/e


a/b = 1.5
b/c = 2.5 => b = 2.5c => bc = 2.5c/d = 5 => c/d = 2
bc/cd = 5

 1.5  2.5 2
a - b - c - d

a/c = 1.5*2.5 = 
c/b = 1/2.5
bc/cd = b/d = 5
cd/bc = d/b = 1/5


*/