Alien Dictionary

LintCode Q 892 - 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:
Input：["wrt","wrf","er","ett","rftt"] ; Output："wertf"
Explanation：
from “wrt”and”wrf” ,we can get ‘t’<’f’
from “wrt”and”er” ,we can get ‘w’<’e’
from “er”and”ett” ,we can get ‘r’<’t’
from “ett”and”rtff” ,we can get ‘e’<’r’
So return “wertf”

Example 2:
Input：["z","x"] ; Output："zx"
Explanation：
from “z” and “x”，we can get ‘z’ < ‘x’
So return “zx”

Notice:

• 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 the smallest in normal lexicographical order

Solution

Solution 1 : DFS

Code:

public String alienOrder(String[] words) {
	
	if (words == null || words.length == 0) return "";

	Map<Character, Set<Character>> graph = buildGraph(words);

	return topologySorting(graph);
}

private Map<Character, Set<Character>> buildGraph(String[] words) {
	
	Map<Character, Set<Character>> graph = new HashMap<>();

	for (String word: words) {
		for (char ch: word.toCharArray()) 
			graph.putIfAbsent(ch, new HashSet<>());
	}

	for (int i = 0; i < words.length - 1; i++) {
		for (int index = 0; index < words[i].length; index++) {
			if (word[i].charAt(index) != word[i + 1].charAt(index)) {
				graph.get(word[i].charAt(index), word[i + 1].charAt(index));
				break;
			}
		}
	}

	return graph;
}

private String topologySorting(Map<Character, Set<Character>> graph) {

	int n = graph.size();
	Map<Character, Integer> order = new HashMap<>();
	for (char ch: graph.keySet()) 
		order.put(ch, 0);
	for (char ch: graph.keySet()) {
		for (char next: graph.get(ch)) 
			order.put(next, order.get(next) + 1);
	}

	Queue<Character> que = new PriorityQueue<>();  // not LinkedList
	for (char ch: order.keySet()) {
		if (order.get(ch) == 0) que.offer(ch);
	}

	StringBuilder sb = new StringBuilder();
	while (!que.isEmpty()) {
		char curr = que.poll();
		sb.append(curr);
		for (char next: graph.get(curr)) {
			map.put(next, map.get(next) - 1);
			if (map.get(next) == 0) que.offer(next);
		}
	}

	if (sb.length() != order.size()) return "";

	return sb.toString();
}

Tip: why using PriorityQueue not just LinkedList
Since for test case ["zy", "zx"], the correct output should be "yxz". If using LinkedList, we get "yzx" which is not correct.