update 269

fishercoder1534 · fishercoder1534 · commit 09b1b99a5ec3 · 2021-07-22T07:54:25.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_269.java b/src/main/java/com/fishercoder/solutions/_269.java
@@ -14,24 +14,26 @@ public static class Solution1 {
          * reference: https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs
          */
         public String alienOrder(String[] words) {
-            Map<Character, Set<Character>> map = new HashMap();
+            Map<Character, Set<Character>> map = new HashMap<>();
             Map<Character, Integer> degree = new HashMap<>();
             String result = "";
             if (words == null || words.length == 0) {
                 return result;
             }
             for (String s : words) {
                 for (char c : s.toCharArray()) {
-                    degree.put(c, 0);//keeps overwriting it, the purpose is to create one entry
-                    //for each letter in the degree map
+                    degree.put(c, 0);
                 }
             }
             for (int i = 0; i < words.length - 1; i++) {
-                String cur = words[i];
+                String curr = words[i];
                 String next = words[i + 1];
-                int length = Math.min(cur.length(), next.length());
-                for (int j = 0; j < length; j++) {
-                    char c1 = cur.charAt(j);
+                if (curr.length() > next.length() && curr.startsWith(next)) {
+                    return "";
+                }
+                int minLen = Math.min(curr.length(), next.length());
+                for (int j = 0; j < minLen; j++) {
+                    char c1 = curr.charAt(j);
                     char c2 = next.charAt(j);
                     if (c1 != c2) {
                         Set<Character> set = new HashSet<>();
@@ -50,17 +52,17 @@ public String alienOrder(String[] words) {
             Queue<Character> queue = new LinkedList<>();
             for (char c : degree.keySet()) {
                 if (degree.get(c) == 0) {
-                    queue.add(c);
+                    queue.offer(c);
                 }
             }
             while (!queue.isEmpty()) {
-                char c = queue.remove();
-                result += c;
-                if (map.containsKey(c)) {
-                    for (char c2 : map.get(c)) {
-                        degree.put(c2, degree.get(c2) - 1);
-                        if (degree.get(c2) == 0) {
-                            queue.add(c2);
+                char curr = queue.poll();
+                result += curr;
+                if (map.containsKey(curr)) {
+                    for (char c : map.get(curr)) {
+                        degree.put(c, degree.get(c) - 1);
+                        if (degree.get(c) == 0) {
+                            queue.offer(c);
                         }
                     }
                 }
diff --git a/src/test/java/com/fishercoder/_269Test.java b/src/test/java/com/fishercoder/_269Test.java
@@ -21,4 +21,10 @@ public void test1() {
         assertEquals("wertf", solution1.alienOrder(words));
     }
 
+    @Test
+    public void test2() {
+        words = new String[]{"abc", "ab"};
+        assertEquals("", solution1.alienOrder(words));
+    }
+
 }

Original file line number	Diff line number	Diff line change
`@@ -21,4 +21,10 @@ public void test1() {`
`21`	`21`	`assertEquals("wertf", solution1.alienOrder(words));`
`22`	`22`	`}`
`23`	`23`
	`24`	`+ @Test`
	`25`	`+ public void test2() {`
	`26`	`+ words = new String[]{"abc", "ab"};`
	`27`	`+ assertEquals("", solution1.alienOrder(words));`
	`28`	`+ }`
	`29`	`+`
`24`	`30`	`}`