首页 > 代码库 > Alien Dictionary
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.
分析：
其实解这题的时候应该能够想到有向图。毕竟每个字符之间存在先后顺序。既然能够想到用有向图解，那么怎么按照顺序把每个字符排列出来，就不难想到用Topological Sort 来解决问题了。下面的代码来自Jiuzhang. 他用了Node来表示每个图中的点，并且记录每个点的入度，当入度为0的时候，表明没有其它点指向改点。
1 public class Solution { 2 public class Node { 3 public int degree; 4 public ArrayList<Integer> neighbour = new ArrayList<Integer>(); 5 void Node() { 6 degree = 0; 7 } 8 } 9 public String alienOrder(String[] words) {10 Node[] node = new Node[26];11 boolean[] happen = new boolean[26];12 for (int i = 0; i < 26; i++) {13 node[i] = new Node();14 }15 //Build the Graph16 for (int i = 0; i < words.length; i++) {17 int startPoint = 0, endPoint = 0;18 for (int j = 0; j < words[i].length(); j++) {19 happen[charToInt(words[i].charAt(j))] = true;20 }21 if (i != words.length - 1) {22 for (int j = 0; j < Math.min(words[i].length(), words[i + 1].length()); j++) {23 if (words[i].charAt(j) != words[i + 1].charAt(j)) {24 startPoint = charToInt(words[i].charAt(j));25 endPoint = charToInt(words[i + 1].charAt(j));26 break;27 }28 }29 }30 if (startPoint != endPoint) {31 node[startPoint].neighbour.add(endPoint);32 node[endPoint].degree++;33 }34 }35 //Topological Sort36 Queue<Integer> queue = new LinkedList<Integer>();37 String ans = "";38 for (int i = 0; i < 26; i++) {39 if (node[i].degree == 0 && happen[i]) {40 queue.offer(i);41 ans = ans + intToChar(i);42 } 43 }44 while (!queue.isEmpty()) {45 int now = queue.poll();46 for (int i : node[now].neighbour) {47 node[i].degree--;48 if (node[i].degree == 0) {49 queue.offer(i);50 ans = ans + intToChar(i);51 }52 }53 }54 for (int i = 0; i < 26; i++) {55 if (node[i].degree != 0) {56 return "";57 }58 }59 return ans;60 }61 public char intToChar(int i) {62 return (char)(‘a‘ + i);63 }64 public int charToInt(char ch) {65 return ch - ‘a‘;66 }67 }
Alien Dictionary
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。