[LeetCode] 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,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

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

Thought process:

Topological sort:

1. Build graph: 
1. a map of character -> set of character.
2. Also get in-degrees for each character. In-degrees will be a map of character -> integer.
2. Topological sort:
1. Loop through in-degrees. Offer the characters with in-degree of 0 to queue.
2. While queue is not empty:
1. Poll from queue. Append to character to result string.
2. Decrease the in-degree of polled character's children by 1.
3. If any child's in-degree decreases to 0, offer it to queue.
3. At last, if result string's length is less than the number of vertices, that means there is a cycle in my graph. The order is invalid.

Solution:

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

class Solution { public String alienOrder(String[] words) { Map<Character, Set<Character>> graph = new HashMap<>(); int[] inDegree = new int[26]; buildGraph(words, graph, inDegree); String order = topologicalSort(graph, inDegree); return order.length() == graph.size() ? order : ""; } private void buildGraph(String[] words, Map<Character, Set<Character>> graph, int[] inDegree) { for (String word : words) { for (char c : word.toCharArray()) { graph.put(c, new HashSet<>()); } } for (int i = 1; i < words.length; i++) { String first = words[i - 1]; String second = words[i]; int length = Math.min(first.length(), second.length()); for (int j = 0; j < length; j++) { char parent = first.charAt(j); char child = second.charAt(j); if (parent != child) { if (!graph.get(parent).contains(child)) { graph.get(parent).add(child); inDegree[child - 'a']++; } break; } } } } private String topologicalSort(Map<Character, Set<Character>> graph, int[] inDegree) { Queue<Character> queue = new LinkedList<>(); for (char c : graph.keySet()) { if (inDegree[c - 'a'] == 0) { queue.offer(c); } } StringBuilder sb = new StringBuilder(); while (!queue.isEmpty()) { char c = queue.poll(); sb.append(c); for (char neighbor : graph.get(c)) { inDegree[neighbor - 'a']--; if (inDegree[neighbor - 'a'] == 0) { queue.offer(neighbor); } } } return sb.toString(); } }

Time complexity:
Say the number of characters in the dictionary (including duplicates) is n. Building the graph takes O(n). Topological sort takes O(V + E). V <= n. E also can't be larger than n. So the overall time complexity is O(n).