[LeetCode][399. Evaluate Division] 4 Approaches: BFS, DFS, Floyd, Union Find

By Long Luo

This article is the solution 4 Approaches: BFS, DFS, Floyd, Union Find of Problem 399. Evaluate Division.

Here shows 4 Approaches to slove this problem: BFS, DFS, Floyd, Union Find.

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// DFS time: O(n^2 * m) space: O(n)
public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> graph = buildGraph(equations, values);

int len = queries.size();
double[] results = new double[len];

for (int i = 0; i < len; i++) {
String u = queries.get(i).get(0);
String v = queries.get(i).get(1);

if (!graph.containsKey(u) || !graph.containsKey(v)) {
results[i] = -1.0;
continue;
}

if (u.equals(v)) {
results[i] = 1.0;
continue;
}

results[i] = bfs(graph, u, v);
}

return results;
}


private static double bfs(Map<String, Map<String, Double>> graph, String u, String v) {
if (graph.get(u).containsKey(v)) {
return graph.get(u).get(v);
}

Set<String> visited = new HashSet<>();

Queue<String[]> queue = new LinkedList<>();
queue.offer(new String[]{u, String.valueOf(1.0)});

visited.add(u);

while (!queue.isEmpty()) {
String[] cur = queue.poll();

String curKey = cur[0];
double curRatio = Double.parseDouble(cur[1]);

if (curKey.equals(v)) {
return curRatio;
}

Map<String, Double> curMap = graph.get(curKey);

for (Map.Entry<String, Double> entry : curMap.entrySet()) {
String nextKey = entry.getKey();
double nextRatio = entry.getValue();

if (visited.contains(nextKey)) {
continue;
}

if (!graph.containsKey(nextKey)) {
continue;
}

double product = curRatio * nextRatio;

if (!graph.get(curKey).containsKey(nextKey)) {
graph.get(curKey).put(nextKey, product);
}

visited.add(nextKey);
queue.offer(new String[]{nextKey, String.valueOf(product)});
}
}

return -1.0;
}

private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
Map<String, Map<String, Double>> graph = new HashMap<>();

int len = equations.size();

for (int i = 0; i < len; i++) {
String u = equations.get(i).get(0);
String v = equations.get(i).get(1);

double w = values[i];

graph.putIfAbsent(u, new HashMap<>());
graph.get(u).put(v, w);

graph.putIfAbsent(v, new HashMap<>());
graph.get(v).put(u, 1.0 / w);
}

return graph;
}

Analysis

  • Time Complexity: \(O(n^2logn)\)
  • Space Complexity: \(O(n^2)\)

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// DFS time: O(n^2 * m) space: O(n)
public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> graph = buildGraph(equations, values);

int len = queries.size();
double[] results = new double[len];

for (int i = 0; i < len; i++) {
String u = queries.get(i).get(0);
String v = queries.get(i).get(1);

if (!graph.containsKey(u) || !graph.containsKey(v)) {
results[i] = -1.0;
continue;
}

if (u.equals(v)) {
results[i] = 1.0;
continue;
}

results[i] = dfs(graph, new HashSet<>(), u, v);
}

return results;
}


private double dfs(Map<String, Map<String, Double>> graph, Set<String> visited, String u, String v) {
if (graph.get(u).containsKey(v)) {
return graph.get(u).get(v);
}

visited.add(u);

Map<String, Double> map = graph.get(u);

for (Map.Entry<String, Double> entry : map.entrySet()) {
String nextKey = entry.getKey();
double nextRatio = entry.getValue();

if (visited.contains(nextKey)) {
continue;
}

double result = dfs(graph, visited, nextKey, v);
if (result != -1.0) {
return result * nextRatio;
}
}

return -1.0;
}

private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
Map<String, Map<String, Double>> graph = new HashMap<>();

int len = equations.size();

for (int i = 0; i < len; i++) {
String u = equations.get(i).get(0);
String v = equations.get(i).get(1);

double w = values[i];

graph.putIfAbsent(u, new HashMap<>());
graph.get(u).put(v, w);

graph.putIfAbsent(v, new HashMap<>());
graph.get(v).put(u, 1.0 / w);
}

return graph;
}

Analysis

  • Time Complexity: \(O(klogn)\)
  • Space Complexity: \(O(n)\)

Floyd

1

Analysis

  • Time Complexity: \(O(nlog(r-l)\)
  • Space Complexity: \(O(1)\)

Union Find

1
2


Analysis

  • Time Complexity: \(O(nlog(r-l)\)
  • Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗