Reference: LeetCode
Difficulty: Hard

Problem

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.

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.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input: [
"z",
"x"
]
Output: "zx"

Input: [
"z",
"x",
"z"
]
Output: ""

Input: ["abc", "abcd"]
Output: "abcd", "bacd" (any order is fine)

Input: ["zx", "zy"]
Output: "xyz" (z can be anywhere)

Input: ["za","zb","ca","cb"]
Output: "abzc" or "azbc"

Analysis

BFS (Topological Sort)

Note:

  • Preprocess: Examine each pair in the words. Try some examples to see how we can gain useful information of a directed edge.
  • Set up all the nodes first, then construct the graph.
  • Do not add duplicate edges and do not calculate in-degrees for duplicate edges.
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
public String alienOrder(String[] words) {
if (words == null || words.length == 0) {
return "";
}

Map<Character, List<Character>> graph = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();

buildGraph(words, graph, indegree);

Queue<Character> queue = new LinkedList<>();

// push all 0-indegree nodes
for (char v : graph.keySet()) {
if (indegree.get(v) == 0) {
queue.offer(v);
}
}

int count = graph.size(); // number of nodes in total
StringBuilder sb = new StringBuilder();
while (queue.size() > 0) {
char v = queue.poll();
sb.append(v);
--count;
List<Character> neighborList = graph.get(v);
// for each neighbor w
for (char w : neighborList) {
int degree = indegree.get(w);
indegree.put(w, degree - 1);
if (degree - 1 == 0) {
queue.offer(w);
}
}
}

if (count == 0) return sb.toString();
else return "";
}


private void buildGraph(String[] words, Map<Character, List<Character>> graph, Map<Character, Integer> indegree) {
// setup all possible nodes
for (int i = 0; i < words.length; ++i) {
for (int j = 0; j < words[i].length(); ++j) {
char ch = words[i].charAt(j);
graph.put(ch, graph.getOrDefault(ch, new ArrayList<>()));
indegree.put(ch, 0);
}
}

// add edges and calculate indegrees
for (int i = 0; i < words.length - 1; ++i) {
String s1 = words[i];
String s2 = words[i + 1];
int j = 0;
while (j < s1.length() && j < s2.length() && s1.charAt(j) == s2.charAt(j)) {
++j;
}
// consider: "abc" vs. "abcd", "abc" vs. "abc", "abcd" vs. "abc" -> no info. gained
if (j < s1.length() && j < s2.length()) {
char c1 = s1.charAt(j);
char c2 = s2.charAt(j);
if (graph.get(c1).contains(c2) == false) { // do not add duplicate edges
graph.get(c1).add(c2);
indegree.put(c2, indegree.getOrDefault(c2, 0) + 1); // indegree
}
}
}
}

Time: $O(NK + V + E)$ where $N$ is the size of words and $K$ is the average length of each word.
Space: $O(V)$