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)$