@@ -14,24 +14,26 @@ public static class Solution1 {
1414 * reference: https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs
1515 */
1616public String alienOrder (String []words ) {
17- Map <Character ,Set <Character >>map =new HashMap ();
17+ Map <Character ,Set <Character >>map =new HashMap <> ();
1818Map <Character ,Integer >degree =new HashMap <>();
1919String result ="" ;
2020if (words ==null ||words .length ==0 ) {
2121return result ;
2222 }
2323for (String s :words ) {
2424for (char c :s .toCharArray ()) {
25- degree .put (c ,0 );//keeps overwriting it, the purpose is to create one entry
26- //for each letter in the degree map
25+ degree .put (c ,0 );
2726 }
2827 }
2928for (int i =0 ;i <words .length -1 ;i ++) {
30- String cur =words [i ];
29+ String curr =words [i ];
3130String next =words [i +1 ];
32- int length =Math .min (cur .length (),next .length ());
33- for (int j =0 ;j <length ;j ++) {
34- char c1 =cur .charAt (j );
31+ if (curr .length () >next .length () &&curr .startsWith (next )) {
32+ return "" ;
33+ }
34+ int minLen =Math .min (curr .length (),next .length ());
35+ for (int j =0 ;j <minLen ;j ++) {
36+ char c1 =curr .charAt (j );
3537char c2 =next .charAt (j );
3638if (c1 !=c2 ) {
3739Set <Character >set =new HashSet <>();
@@ -50,17 +52,17 @@ public String alienOrder(String[] words) {
5052Queue <Character >queue =new LinkedList <>();
5153for (char c :degree .keySet ()) {
5254if (degree .get (c ) ==0 ) {
53- queue .add (c );
55+ queue .offer (c );
5456 }
5557 }
5658while (!queue .isEmpty ()) {
57- char c =queue .remove ();
58- result +=c ;
59- if (map .containsKey (c )) {
60- for (char c2 :map .get (c )) {
61- degree .put (c2 ,degree .get (c2 ) -1 );
62- if (degree .get (c2 ) ==0 ) {
63- queue .add ( c2 );
59+ char curr =queue .poll ();
60+ result +=curr ;
61+ if (map .containsKey (curr )) {
62+ for (char c :map .get (curr )) {
63+ degree .put (c ,degree .get (c ) -1 );
64+ if (degree .get (c ) ==0 ) {
65+ queue .offer ( c );
6466 }
6567 }
6668 }