269 Alien Dict
我们重点分析时间复杂度，我们假设拓扑图中有n个节点和m条边。下面我们首先分析下DFS的复杂度：DFS会遍历所有的节点和所有的边，因此复杂度很好分析那就是O(n + m)，这是一个线性时间，比较好的算法。
BFS方式，首先需要init一个拥有n个节点的列表，并且需要遍历一遍图中的边逻辑；这个方式的时间复杂度也是O(n + m)，同样是一个线性时间
Topo-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
|
class {
private Map<Character, Set<Character>> graph;
private Map<Character, Integer> inDegree;
private String[] words;
public String alienOrder(String[] words) {
if (words == null || words.length == 0) return "";
this.words = words;
StringBuilder sb = new StringBuilder();
buildGraph();
Queue<Character> queue = new LinkedList<>();
for (Character c : inDegree.keySet()) {
if (inDegree.get(c) == 0) {
queue.offer(c);
}
}
while (!queue.isEmpty()) {
char cur = queue.poll();
sb.append(cur);
for (char next : graph.getOrDefault(cur, new LinkedHashSet<>())) {
if (inDegree.get(next) == 1) {
queue.offer(next);
}
inDegree.put(next, inDegree.get(next) - 1);
}
}
if (inDegree.size() != sb.length()) {
return "";
}
return sb.toString();
}
public void buildGraph() {
graph = new HashMap<>();
inDegree = new HashMap<>();
for (String word : words) {
for (Character c : word.toCharArray()) {
inDegree.putIfAbsent(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
char[] arr1 = words[i].toCharArray();
char[] arr2 = words[i + 1].toCharArray();
int len = Math.min(arr1.length, arr2.length);
for (int j = 0; j < len; j++) {
char a = arr1[j];
char b = arr2[j];
if (a != b) {
graph.putIfAbsent(a, new LinkedHashSet<>());
if (!graph.get(a).contains(b)) {
graph.get(a).add(b);
inDegree.put(b, inDegree.get(b) + 1);
}
break;
}
}
}
}
}
|
Topo-DFS:
建图基本和bfs法一样，唯一区别是需要一个visit map来知道三种状态：unseen,visiting和visited, 不需要indegree的map了
注意两点：
- visited的条件，也就是入结果的条件是这个char的邻居都被visited了
- 结果放入sb的顺序是和topological order反的，所以最后输出时候要reverse sb
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
|
class {
private Map<Character, Set<Character>> graph;
private Map<Character, Integer> visit;
private String[] words;
public String alienOrder(String[] words) {
this.words = words;
visit = new HashMap<>();
graph = new HashMap<>();
if (words == null || words.length == 0) {
return "";
}
buildGraph();
StringBuilder sb = new StringBuilder();
for (char c : visit.keySet()) {
if (!dfs(c, sb)) return "";
}
System.out.println("reverse of res is: " + sb.toString());
return sb.reverse().toString();
}
private boolean dfs(char cur, StringBuilder sb) {
if (visit.get(cur) == 1) {
return true;
}
if (visit.get(cur) == 0) {
return false;
}
visit.put(cur, 0);
for (char next : graph.getOrDefault(cur, new HashSet<>())) {
if (!dfs(next, sb)) {
return false;
}
}
visit.put(cur, 1);
sb.append(cur);
return true;
}
public void buildGraph() {
for (String word : words) {
for (char c : word.toCharArray()) {
visit.put(c, -1);
}
}
for (int i = 0; i < words.length - 1; i++) {
char[] arr1 = words[i].toCharArray();
char[] arr2 = words[i + 1].toCharArray();
int len = Math.min(arr1.length, arr2.length);
for (int j = 0; j < len; j++) {
char one = arr1[j];
char two = arr2[j];
graph.putIfAbsent(one, new HashSet<>());
if (one != two) {
graph.get(one).add(two);
break;
}
}
}
}
}
|
1
2
3
4
5
6
|
public static void main(String[] args) {
String[] input = {"ab", "bc", "cde"};
Solution sol = new Solution();
System.out.println("order is: " + sol.alienOrder(input));
}
|
近期评论