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 words from the dictionary, wherewords are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

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

The correct order is: "wertf".

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

Solution 1: Build the graph and then topo sort.

 public class Solution {  
   public String alienOrder(String[] words) {  
     Map<Character, Set<Character>> map=new HashMap<>();  
     String pre="";  
     for (String s: words) {  
       for (int i=0; i<s.length(); i++) {  
         if (!map.containsKey(s.charAt(i))) {  
           Set<Character> set=new HashSet<>();  
           map.put(s.charAt(i),set);  
         }  
       }  
       int min=Math.min(s.length(),pre.length());  
       for (int i=0; i<min; i++) {  
         if (pre.charAt(i)!=s.charAt(i)) {  
           map.get(pre.charAt(i)).add(s.charAt(i));  
           break;//only judge the 1st different char  
         }  
       }  
       pre=s;  
     }  
     Set<Character> marked=new HashSet<>();  
     Set<Character> onStack=new HashSet<>();  
     boolean[] hasCycle=new boolean[1];  
     StringBuilder sb=new StringBuilder();  
     for (Character v: map.keySet()) {  
       if (!marked.contains(v)) dfs(map,v,marked,onStack,hasCycle,sb);  
     }  
     if (hasCycle[0]) return "";  
     return sb.reverse().toString();  
   }  
   private void dfs(Map<Character, Set<Character>> map, Character v, Set<Character> marked, Set<Character> onStack, boolean[] hasCycle, StringBuilder sb) {  
     marked.add(v);  
     onStack.add(v);  
     for (Character w: map.get(v)) {  
       if (hasCycle[0]) return;  
       else if (!marked.contains(w)) dfs(map,w,marked,onStack,hasCycle,sb);  
       else if (onStack.contains(w)) hasCycle[0]=true;  
     }  
     sb.append(v);  
     onStack.remove(v);  
   }  
 }