269. Alien Dictionary

发表于 | 分类于

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

1
2
3
4
5
6
7
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: “wertf”.

Example 2:
Given the following words in dictionary,

1
2
3
4
[
  "z",
  "x"
]

The correct order is: “zx”.

Example 3:
Given the following words in dictionary,

1
2
3
4
5
[
  "z",
  "x",
  "z"
]

The order is invalid, so return “”.

Note:
You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

解法1： Topological sort

此题的难点是看出来这是一题graph。
本质上这题的意思是不同的字符之间有顺序，而我们要找出来这个隐藏的顺序。
那么graph的node就是可能的字符,用一个26大小的array记录每一个字符的入度和出度。
然后遍历相邻的两个string，搜索直到两个字符不一样为止，然后用一个adjacent matrix记录两者之间的关系
同时增加后一个字符的入度。
等完成了之后只需要用一个queue做一个topological sort就可以了。

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
class Solution {
public String alienOrder(String[] words) {
    List<Set<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < 26; i++) {
        adj.add(new HashSet<Integer>());
    }
    int[] degree = new int[26];
    Arrays.fill(degree, -1);
    for (int i = 0; i < words.length; i++) {
        for (char c : words[i].toCharArray()) {
            if (degree[c - 'a'] < 0) {
                degree[c - 'a'] = 0;
            }
        }
        if (i > 0) {
            String w1 = words[i - 1], w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                int c1 = w1.charAt(j) - 'a', c2 = w2.charAt(j) - 'a';
                if (c1 != c2) {
                    if (!adj.get(c1).contains(c2)) {
                        adj.get(c1).add(c2);
                        degree[c2]++;
                    }
                    break;
                }
                if (j == w2.length() - 1 && w1.length() > w2.length()) { // "abcd" -> "ab"
                    return "";
                }
            }
        }
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < degree.length; i++) {
        if (degree[i] == 0) {
            q.add(i);       
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        int i = q.poll();
        sb.append((char) ('a'  + i));
        for (int j : adj.get(i)) {
            degree[j]--;
            if (degree[j] == 0) {
                q.add(j);        
            }
        }
    }
    for (int d : degree) {
        if (d > 0) {
            return "";
        }
    }
    return sb.toString();
}
}