Created
April 15, 2016 05:47
-
-
Save cangoal/6f9b9deee67ce08591769dd8d62bc5e0 to your computer and use it in GitHub Desktop.
LeetCode - Alien Dictionary
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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!