首页 > 代码库 > 269. Alien Dictionary
269. Alien Dictionary
本质上就是topological sort.
1. 统计所有的点
对于每一个string,把所有的字母都加入indegree
2. 构建图，统计indegree
对于没连续的一组str，找到第一个不同的字母，把后一个加入前一个字母的neighbor，并且给后一个字母indegree+1.
需要注意的是，如果要检查后一个字母是不是已经在第一个字母的neighbor，如果不是再做后续操作
3. 遍历图
注意可能没有邻节点
4. 检查是不是所有点都访问到了，返回结果
1 public String alienOrder(String[] words) { 2 if(words.length < 1) { 3 return ""; 4 } 5 String res = ""; 6 Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>(); 7 Map<Character, Integer> indegree = new HashMap<Character, Integer>(); 8 for(String s: words) { 9 for(char c: s.toCharArray()) {10 indegree.put(c, 0);11 }12 }13 for(int i = 0; i < words.length - 1; i++) {14 String cur = words[i];15 String next = words[i + 1];16 int len = Math.min(cur.length(), next.length());17 for(int j = 0; j < len; j++) {18 char c1 = cur.charAt(j);19 char c2 = next.charAt(j);20 if(c1 != c2) {21 Set<Character> neighbors = map.get(c1);22 if(neighbors == null) {23 neighbors = new HashSet<Character>();24 }25 if(!neighbors.contains(c2)) {26 neighbors.add(c2);27 map.put(c1, neighbors);28 indegree.put(c2, indegree.get(c2) + 1);29 }30 break;31 }32 }33 }34 Queue<Character> queue = new LinkedList<Character>();35 for(Character c: indegree.keySet()) {36 if(indegree.get(c) == 0) {37 queue.offer(c);38 }39 }40 while(!queue.isEmpty()) {41 Character c = queue.poll();42 res += c;43 Set<Character> neighbors = map.get(c);44 if(neighbors == null) {45 continue;46 }47 for(Character x: neighbors) {48 indegree.put(x, indegree.get(x) - 1);49 if(indegree.get(x) == 0) {50 queue.offer(x);51 }52 }53 }54 return indegree.size() == res.length()? res: "";55 }
269. Alien Dictionary
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。