private Set<Character> vertices = new HashSet<>();

private Set<Character>[] graph = new Set[26];

/**

public String alienOrder(String[] words) {

initMap(words);

updateOrderMap(words);

StringBuilder sb = new StringBuilder();

boolean[] visited = new boolean[26];

for (char key: vertices) {

if (!visited[key - 'a']) {

if (!helper(key, new HashSet<Character>(), visited, sb)) return "";

}

}

return sb.reverse().toString();

}

private boolean helper(Character key, Set<Character> path, boolean[] visited, StringBuilder sb) {

visited[key - 'a'] = true;

path.add(key);

for (Character c: graph[key - 'a']) {

if (path.contains(c)) return false;

if (!visited[c - 'a']) {

if (!helper(c, path, visited, sb)) return false;

}

}

sb.append(key);

path.remove(key);

return true;

}

private void initMap(String[] words) {

for (String word: words) {

for (char c: word.toCharArray()) {

if (!vertices.contains(c)) {

vertices.add(c);

graph[c - 'a'] = new HashSet<Character>();

}

}

}

}

private void updateOn(String word1, String word2) {

int len = Math.min(word1.length(), word2.length());

for (int i=0; i<len; i++) {

if (word1.charAt(i) != word2.charAt(i)) {

graph[word1.charAt(i) - 'a'].add(word2.charAt(i));

return;

}

}

}

private void updateOrderMap(String[] dicts) {

initMap(dicts);

for (int i=0; i<dicts.length-1; i++) {

updateOn(dicts[i], dicts[i+1]);

}

}

/**

private int[] incomming = new int[26];

public String alienOrder2(String[] words) {

initMap(words);

updateOrderMap(words);

for (Character v: vertices) {

Set<Character> adjs = graph[v - 'a'];

if (adjs != null) {

for (Character c: adjs) {

incomming[c - 'a']++;

}

}

}

Queue<Character> q = new LinkedList<>();

for (Character c: vertices) {

if (incomming[c - 'a'] == 0) {

q.add(c);

}

}

int visited = 0;

StringBuilder sb = new StringBuilder();

while (!q.isEmpty()) {

char c = q.remove();

sb.append(c);

for (Character next: graph[c - 'a']) {

incomming[next - 'a']--;

if (incomming[next - 'a'] == 0) {

q.add(next);

}

}

visited++;

}

if (visited != vertices.size()) return "";

return sb.toString();

}

/**

private final int N = 26;

public String alienOrder3(String[] words) {

boolean[][] adj = new boolean[N][N];

int[] visited = new int[N];

buildGraph(words, adj, visited);

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(adj[i][j]) { // connected

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;

}

}

}

}

}