Skip to content

Instantly share code, notes, and snippets.

@cangoal
Created April 15, 2016 05:47
Show Gist options
  • Save cangoal/6f9b9deee67ce08591769dd8d62bc5e0 to your computer and use it in GitHub Desktop.
Save cangoal/6f9b9deee67ce08591769dd8d62bc5e0 to your computer and use it in GitHub Desktop.
LeetCode - 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, where words 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:
// You may assume all letters are in lowercase.
// If the order is invalid, return an empty string.
// There may be multiple valid order of letters, return any one of them is fine.
public String alienOrder(String[] words) {
if(words == null || words.length == 0) return "";
StringBuilder sb = new StringBuilder();
Map<Character, Integer> degree = new HashMap<Character, Integer>();
Map<Character, Set<Character>> toMap = new HashMap<Character, Set<Character>>();
for(String s: words){
for(char c: s.toCharArray()){
degree.put(c, 0);
}
}
for(int i = 0; i < words.length - 1; i++){
int length = Math.min(words[i].length(), words[i+1].length());
for(int j = 0; j < length; j++){
char cur = words[i].charAt(j), next = words[i+1].charAt(j);
if(cur == next) continue;
if(toMap.containsKey(cur)){
if(!toMap.get(cur).contains(next)){
toMap.get(cur).add(next);
degree.put(next, degree.get(next) + 1);
}
} else {
Set<Character> set = new HashSet<Character>();
set.add(next);
toMap.put(cur, set);
degree.put(next, degree.get(next) + 1);
}
break;
}
}
Queue<Character> queue = new LinkedList<Character>();
for(char c : degree.keySet())
if(degree.get(c) == 0)
queue.offer(c);
while(!queue.isEmpty()){
char cur = queue.poll();
sb.append(cur);
if(!toMap.containsKey(cur)) continue;
for(Character next : toMap.get(cur)){
degree.put(next, degree.get(next) - 1);
if(degree.get(next) == 0){
queue.add(next);
}
}
}
if(sb.length() != degree.size()) return "";
return sb.toString();
}
@AbhinavMehrotra
Copy link

It would have been much easier to understand this code if there was some comments/documentation. Could you please add some text about this logic? Thanks in advance!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment