BiruLyu
8/10/2017 - 6:34 PM

## 269. Alien Dictionary(#).java

``````
public class Solution {
private final int N = 26;
public String alienOrder(String[] words) {
int[] visited = new int[N];

StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
if(visited[i] == 0) {                 // unvisited
if(!dfs(adj, visited, sb, i)) return "";
}
}
return sb.reverse().toString();
}

public boolean dfs(boolean[][] adj, int[] visited, StringBuilder sb, int i) {
visited[i] = 1;                            // 1 = visiting
for(int j = 0; j < N; j++) {
if(visited[j] == 1) return false;  // 1 => 1, cycle
if(visited[j] == 0) {              // 0 = unvisited
if(!dfs(adj, visited, sb, j)) return false;
}
}
}
visited[i] = 2;                           // 2 = visited
sb.append((char) (i + 'a'));
return true;
}

public void buildGraph(String[] words, boolean[][] adj, int[] visited) {
Arrays.fill(visited, -1);                 // -1 = not even existed
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) {
adj[c1 - 'a'][c2 - 'a'] = true;
break;
}
}
}
}
}
}``````
``````public class Solution {
private String topologicalSort(Map<Character, Set<Character>> map, Map<Character, Integer> degree) {
String result = "";
for(char c: degree.keySet()){
if(degree.get(c) == 0) q.offer(c);
}
while(!q.isEmpty()){
char c = q.poll();
result += c;
if(map.containsKey(c)){
for(char c2: map.get(c)){
degree.put(c2,degree.get(c2)-1);
}
}
}
if(result.length() != degree.size()) return "";
return result;
}
public String alienOrder(String[] words) {
if (words == null || words.length < 1) return "";
int len = words.length;
Map<Character, Set<Character>> adjList = new HashMap<>();
Map<Character, Integer> nodes = new HashMap<>();
for(String s: words){
for(char c: s.toCharArray()){
nodes.put(c,0);
}
}
for(int j = 0; j < len - 1; j++) {
char[] a = words[j].toCharArray();
char[] b = words[j + 1].toCharArray();
for (int i = 0; i < a.length && i < b.length; i++) {
if (a[i] != b[i]) {