|
| 1 | +packagehard; |
| 2 | + |
| 3 | +importjava.util.*; |
| 4 | + |
| 5 | +/** |
| 6 | + * Created by SteveSun on 9/29/16. |
| 7 | + */ |
| 8 | +publicclassAlienDictionary { |
| 9 | + |
| 10 | +/**With this code, this test case: ["wrtkj","wrt"], expected "", my output: "jkrtw", this is a new test case that got added |
| 11 | + * on 9/29/2016, it's 113/115 test cases. |
| 12 | + * And all code on the Discuss board fail by this test case.*/ |
| 13 | +publicstaticStringalienOrder(String[]words) { |
| 14 | +Set<String>orders =newHashSet(); |
| 15 | +Set<Character>orderChar =newHashSet(); |
| 16 | +for(inti =0;i <words.length-1;i++){ |
| 17 | +for(intj =0;j <Math.min(words[i].length(),words[i+1].length());j++){ |
| 18 | +if(words[i].charAt(j) !=words[i+1].charAt(j)){ |
| 19 | +Stringorder ="" +words[i].charAt(j) +words[i+1].charAt(j); |
| 20 | +StringreverseOrder ="" +words[i+1].charAt(j) +words[i].charAt(j); |
| 21 | +if(!orders.contains(order)) { |
| 22 | +orders.add(order); |
| 23 | +orderChar.add(words[i].charAt(j)); |
| 24 | +orderChar.add(words[i+1].charAt(j)); |
| 25 | + } |
| 26 | +if(orders.contains(reverseOrder))return""; |
| 27 | +break; |
| 28 | + } |
| 29 | + } |
| 30 | + } |
| 31 | + |
| 32 | +//computer all letters that appeared: |
| 33 | +Set<Character>appearedLetters =newHashSet(); |
| 34 | +for(Stringword :words){ |
| 35 | +char[]cs =word.toCharArray(); |
| 36 | +for(charc :cs){ |
| 37 | +appearedLetters.add(c); |
| 38 | + } |
| 39 | + } |
| 40 | + |
| 41 | +for(charc :appearedLetters){ |
| 42 | +if(!orderChar.contains(c))return""; |
| 43 | + } |
| 44 | + |
| 45 | +int[]indegree =newint[26]; |
| 46 | +for(Stringorder :orders){ |
| 47 | +indegree[order.charAt(1) -'a']++; |
| 48 | + } |
| 49 | + |
| 50 | +//use a set to store all characters that have zero indegrees |
| 51 | +Set<Character>zeroDegree =newHashSet(); |
| 52 | +Queue<Character>q =newLinkedList(); |
| 53 | +for(inti =0;i <26;i++){ |
| 54 | +if(indegree[i] ==0 &&appearedLetters.contains((char) (i+'a'))) { |
| 55 | +zeroDegree.add((char) (i+'a')); |
| 56 | +q.offer((char) (i+'a')); |
| 57 | + } |
| 58 | + } |
| 59 | + |
| 60 | +while(!zeroDegree.isEmpty()){ |
| 61 | +Iterator<Character>iter =zeroDegree.iterator(); |
| 62 | +charletter =iter.next(); |
| 63 | +zeroDegree.remove(letter); |
| 64 | +for(Stringorder :orders){ |
| 65 | +if(order.charAt(0) ==letter){ |
| 66 | +indegree[order.charAt(1)-'a']--; |
| 67 | +if(indegree[order.charAt(1)-'a'] ==0){ |
| 68 | +zeroDegree.add(order.charAt(1)); |
| 69 | +q.offer(order.charAt(1)); |
| 70 | + } |
| 71 | + } |
| 72 | + } |
| 73 | + } |
| 74 | + |
| 75 | +for(inti :indegree){ |
| 76 | +if(i !=0)return""; |
| 77 | + } |
| 78 | + |
| 79 | +StringBuildersb =newStringBuilder(); |
| 80 | +while(!q.isEmpty()){ |
| 81 | +sb.append(q.poll()); |
| 82 | + } |
| 83 | +returnsb.toString(); |
| 84 | + } |
| 85 | + |
| 86 | +publicstaticvoidmain(String ...args){ |
| 87 | +System.out.println("Hello world."); |
| 88 | +String[]words =newString[]{"wrt","wrf","er","ett","rftt"}; |
| 89 | +Stringorder =alienOrder(words); |
| 90 | +System.out.print(order); |
| 91 | + } |
| 92 | +} |