## 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:

``````Input:

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

Output: "wertf"
``````

Example 2:

``````Input:

[
"z",
"x"
]

Output: "zx"
``````

Example 3:

``````Input:

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

Output:""
Explanation: 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.

Thoughts:

1. BFS: construct the relative ordering between characters by observing the first difference of the character from the two consecutive inputs-> Then construct the relative ordering using BFS (with queue)
2. DFS: Check whether there is a cycle in the graph when building the return answer.

1. state = -1, not exist

2. 0: Exist. Non-visited.

3. 1: Visiting

4. 2: Visited

3. Topological Sort:

Code: BFS

``````class Solution {
public String alienOrder(String[] words) {
Map <Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
Map <Character, Integer> level = new HashMap <Character, Integer>();
for(String word : words)
for (char c : word.toCharArray())
level.put(c, 0);

// find the dependency by pairwise comparason
for(int i = 0; i < words.length - 1; i++){
String cur = words[i];
String next = words[i + 1];
int len = Math.min(cur.length(), next.length());

// search for char difference to find the relative order
for (int j = 0; j < len; j++){
char c1 = cur.charAt(j);
char c2 = next.charAt(j);
if(c1 != c2){
// put the order into the map
Set<Character> set = map.getOrDefault(c1, new HashSet<Character>());
if(!set.contains(c2)){
map.put(c1, set);
// increasing the processing priority
level.put(c2, level.get(c2) + 1);
}
break;
}
}
}

// BFS
for(char c: level.keySet())

String res = "";
while(!q.isEmpty()){
char c = q.remove();
res += c;
// propagate the dependency, increase its neighbors' priority
if(map.containsKey(c)){
for(char succ: map.get(c)){
level.put(succ, level.get(succ) - 1);
}
}
}
// check whether all dependency has been meet: all the priority in level has become 0
if(res.length() != level.size()) return "";
return res;

}
}
``````

Code: DFS

``````class Solution {
private final int N = 26;
public String alienOrder(String[] words) {
boolean [][] adj = new boolean [N][N];
int [] visited = new int [N];
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < N; i++){
if(visited[i]==0){ // unvisited
}
}

return sb.reverse().toString();
}

private boolean dfs( boolean [][] adj, int[] visited, StringBuilder sb, int i){
visited[i] = 1; // mark as visiting
// checking its neightbor
for(int j = 0; j < N; j++){
if(visited[j] == 1) return false; // cycle detection
if (visited[j] == 0){ // only visit unvisited nodes that are "larger" in the ordering
if(!dfs(adj, visited, sb, j)) return false;
}
}
}

visited[i] = 2; // mark as visited
sb.append((char)(i + 'a'));
return true;
}

private void buildGraph(String[] words, boolean[][] adj, int[] visited){
Arrays.fill(visited, -1);
for(int i = 0; i < words.length; i++){
for(char c: words[i].toCharArray()) visited[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++){
char c1 = w1.charAt(j), c2 = w2.charAt(j);
if(c1 != c2){
// imposing the ordering
adj[c1 - 'a'][c2 - 'a'] = true;
break;
}
}
}
}
}
}
``````

Code: Topological Sort

``````  class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
# build the graph using greater and less default dict
smaller = collections.defaultdict(set)
larger = collections.defaultdict(set)

for i in range(len(words) - 1):
minlen = min(len(words[i]), len(words[i + 1]))
j = 0
while j < minlen and words[i][j] == words[i + 1][j]:
j += 1

if j < minlen:

charset = set(''.join(words))
res = []

deque = collections.deque([x for x in charset if x not in larger])

while deque:
i = deque.popleft()
if i in smaller:
for j in smaller[i]:
larger[j].remove(i)
if len(larger[j]) == 0:
del larger[j]