399 Evaluate Division

399. Evaluate Division​
1. Question
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:
1
equations = [ ["a", "b"], ["b", "c"] ],
2
values = [2.0, 3.0],
3
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
Copied!
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
2. Implementation
(1) DFS
1
class Solution {
2
    class Edge {
3
        String val;
4
        double weight;
5
​
6
        public Edge(String val, double weight) {
7
            this.val = val;
8
            this.weight = weight;
9
        }
10
    }
11
​
12
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
13
        double[] res = new double[queries.length];
14
​
15
        if (equations.length == 0 || equations[0].length == 0) {
16
            return res;
17
        }
18
​
19
        Map<String, List<Edge>> adjList = new HashMap<>();
20
​
21
        for (int i = 0; i < equations.length; i++) {
22
            String vertex1 = equations[i][0];
23
            String vertex2 = equations[i][1];
24
​
25
            Edge edge1 = new Edge(vertex2, values[i]);
26
            Edge edge2 = new Edge(vertex1, 1 / values[i]);
27
​
28
            if (adjList.containsKey(vertex1)) {
29
                adjList.get(vertex1).add(edge1);
30
            }
31
            else {
32
                List<Edge> edges = new ArrayList<>();
33
                edges.add(edge1);
34
                adjList.put(vertex1, edges);
35
            }
36
​
37
            if (adjList.containsKey(vertex2)) {
38
                adjList.get(vertex2).add(edge2);
39
            }
40
            else {
41
                List<Edge> edges = new ArrayList<>();
42
                edges.add(edge2);
43
                adjList.put(vertex2, edges);
44
            }
45
        }
46
​
47
        for (int i = 0; i < queries.length; i++) {
48
            String start = queries[i][0];
49
            String end = queries[i][1];
50
            Set<String> visited = new HashSet<>();
51
            dfs(start, end, 1.0, i, visited, adjList, res);
52
            if (res[i] == 0 && !start.equals(end)) {
53
                res[i] = -1.0;
54
            }
55
        }
56
        return res;
57
    }
58
​
59
    public void dfs(String start, String end, double value, int index, Set<String> visited, Map<String, List<Edge>> adjList, double[] res) {
60
        if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
61
            res[index] = -1.0;
62
            return;
63
        }
64
​
65
        if (start.equals(end)) {
66
            res[index] = value;
67
            return;
68
        }
69
​
70
        if (visited.contains(start)) {
71
            return;
72
        }
73
​
74
​
75
        visited.add(start);
76
        List<Edge> edges = adjList.get(start);
77
​
78
        for (Edge edge : edges) {
79
            dfs(edge.val, end, value * edge.weight, index, visited, adjList, res);
80
        }
81
    }
82
}
Copied!
(2) BFS 
1
class Solution {
2
    class Edge {
3
        String val;
4
        double weight;
5
​
6
        public Edge(String val, double weight) {
7
            this.val = val;
8
            this.weight = weight;
9
        }
10
    }
11
​
12
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
13
        double[] res = new double[queries.length];
14
​
15
        if (equations.length == 0 || equations[0].length == 0) {
16
            return res;
17
        }
18
​
19
        Map<String, List<Edge>> adjList = new HashMap<>();
20
​
21
        for (int i = 0; i < equations.length; i++) {
22
            String vertex1 = equations[i][0];
23
            String vertex2 = equations[i][1];
24
​
25
            Edge edge1 = new Edge(vertex2, values[i]);
26
            Edge edge2 = new Edge(vertex1, 1 / values[i]);
27
​
28
            if (adjList.containsKey(vertex1)) {
29
                adjList.get(vertex1).add(edge1);
30
            }
31
            else {
32
                List<Edge> edges = new ArrayList<>();
33
                edges.add(edge1);
34
                adjList.put(vertex1, edges);
35
            }
36
​
37
            if (adjList.containsKey(vertex2)) {
38
                adjList.get(vertex2).add(edge2);
39
            }
40
            else {
41
                List<Edge> edges = new ArrayList<>();
42
                edges.add(edge2);
43
                adjList.put(vertex2, edges);
44
            }
45
        }
46
​
47
        for (int i = 0; i < queries.length; i++) {
48
            String start = queries[i][0];
49
            String end = queries[i][1];
50
            Set<String> visited = new HashSet<>();
51
            bfs(start, end, i, visited, adjList, res);
52
            if (res[i] == 0 && !start.equals(end)) {
53
                res[i] = -1.0;
54
            }
55
        }
56
        return res;
57
    }
58
​
59
    public void bfs(String start, String end, int index, Set<String> visited, Map<String, List<Edge>> adjList, double[] res) {
60
        if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
61
            res[index] = -1.0;
62
            return;
63
        }
64
​
65
        Queue<String> queue = new LinkedList<>();
66
        Queue<Double> values = new LinkedList<>();
67
​
68
        queue.add(start);
69
        values.add(1.0);
70
​
71
        while (!queue.isEmpty()) {
72
            String curVertex = queue.remove();
73
            double curValue = values.remove();
74
​
75
            if (!adjList.containsKey(curVertex)) {
76
                res[index] = -1.0;
77
                return;
78
            }
79
​
80
            if (curVertex.equals(end)) {
81
                res[index] = curValue;
82
                return;
83
            }
84
​
85
            if (visited.contains(curVertex)) {
86
                continue;
87
            }
88
​
89
            visited.add(curVertex);
90
​
91
            for (Edge edge : adjList.get(curVertex)) {
92
                String nextVertex = edge.val;
93
                queue.add(nextVertex);
94
                double nextValue = curValue * edge.weight;
95
                values.add(nextValue);
96
            }
97
        }
98
    }
99
}
Copied!
3. Time & Space Complexity
DFS:
BFS:
364 Nested List Weight Sum II
417 Pacific Atlantic Water Flow
Last modified 2yr ago
Copy link
Contents
399. Evaluate Division
1. Question
2. Implementation
3. Time & Space Complexity
399. Evaluate Division​

1. Question

2. Implementation

3. Time & Space Complexity

399. Evaluate Division
