脚本宝典收集整理的这篇文章主要介绍了[剑指 Offer II 114. 外星文字典] 拓扑排序,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
import java.util.*; class Solution { public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.alienOrder(new String[]{ "ac","ab","zc","zb" })); } public String alienOrder(String[] words) { int len = words.length; Set<Integer> flag = new HashSet<>(); for (int i = 0; i < len; i++) { for(int j =0;j<words[i].length();j++){ flag.add(words[i].charAt(j)-'a'); } } Set<Integer>[] g = new HashSet[26]; Arrays.setAll(g,e->new HashSet<>()); int[] ingress = new int[26]; Set<List<Integer>> edge = new HashSet<>(); for(int i = 0;i<len-1;i++){ String a = words[i]; String b = words[i+1]; int alen = a.length(); int blen = b.length(); int min = Math.min(alen,blen); boolean find = false; int j = 0; for(j=0;j<min;j++){ if( a.charAt(j) != b.charAt(j)){ find = true; break; } } if(!find ) { if(alen > blen){ return ""; } }else{ int d1 = a.charAt(j) - 'a'; int d2 = b.charAt(j) - 'a'; g[d1].add(d2); if(!edge.contains(Arrays.asList(d1,d2))) { ingress[d2]++; edge.add(Arrays.asList(d1,d2)); } } } StringBuilder ans = build(g,ingress,flag); return ans.toString(); } public StringBuilder build(Set<Integer>[] g,int[] ingress,Set<Integer> flag) { ArrayDeque<Integer> queue = new ArrayDeque<Integer>(); for (int i = 0; i < 26; i++) { if (flag.contains(i) && ingress[i] == 0) { queue.offer(i); } } StringBuilder sb = new StringBuilder(); while (!queue.isEmpty()) { int u = queue.poll(); if (ingress[u] == 0) { sb.append((char) ('a' + u)); } for (Integer v : g[u]) { ingress[v]--; if (ingress[v] == 0) { queue.offer(v); } } } if( flag.size() != sb.length()) { return new StringBuilder(""); } return sb; } }
以上是脚本宝典为你收集整理的[剑指 Offer II 114. 外星文字典] 拓扑排序全部内容,希望文章能够帮你解决[剑指 Offer II 114. 外星文字典] 拓扑排序所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。