# 2 general Solutions based on BFS topological sort

• ``````//Solution 1: build successor set for every character
public String alienOrder(String[] words) {
Map<Character, Set<Character>> successorMap=new HashMap<Character, Set<Character>>();
Set<Character> CharacterSet=new HashSet<Character>();
for(int i=0; i<words.length; i++){
for(int j=0; j<words[i].length(); j++)
}
//Build char->successorSet
for(int i=0; i<words.length-1; i++){
String cur=words[i],next = words[i+1];
int length=Math.min(cur.length(), next.length());
for(int j=0; j<length; j++){
char c1=cur.charAt(j),c2 = next.charAt(j);
if(c1!=c2){
Set<Character> successor=new HashSet<Character>();
if(successorMap.containsKey(c1)) successor=successorMap.get(c1);
if(!successor.contains(c2)){
successorMap.put(c1, successor);
}
break;
}
}
}
for(char c: CharacterSet)
StringBuilder result = new StringBuilder();
while(!bfs.isEmpty()){
char c=bfs.remove(); result.append(c);
for(char charkey: successorMap.keySet()){
Set<Character> successor = successorMap.get(charkey);
if(successor.contains(c)){
successor.remove(c);
}
}
}
if(result.length()!=CharacterSet.size()) return "";
return result.reverse().toString();
}

//Solution 2: build predecessor set for every character
public String alienOrder2(String[] words) {
Map<Character, Set<Character>> predecessorMap=new HashMap<Character, Set<Character>>();
Set<Character> CharacterSet=new HashSet<Character>();
for(String s: words)
for(char c: s.toCharArray())
//Build char->predecessorSet
for(int i=0; i<words.length-1; i++){
String cur=words[i],next=words[i+1];
int length=Math.min(cur.length(), next.length());
for(int j=0; j<length; j++){
char c1=cur.charAt(j),c2 = next.charAt(j);
if(c1!=c2){
Set<Character> predecessor=new HashSet<Character>();
if(predecessorMap.containsKey(c2)) predecessor=predecessorMap.get(c2);
if(!predecessor.contains(c1)){
predecessorMap.put(c2, predecessor);
}
break;
}
}
}
//put into Queue all Characters without predecessor
for(char c: CharacterSet)
StringBuilder result = new StringBuilder();
//BFS toplocial sort
while(!bfs.isEmpty()){
char c=bfs.poll();
result.append(c);
for(char charkey: predecessorMap.keySet()){
Set<Character> predecessor = predecessorMap.get(charkey);
if(predecessor.contains(c)){
predecessor.remove(c);