update 269

fishercoder1534 · fishercoder1534 · commit d1213da50de2 · 2024-07-04T08:58:53.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/firstthousand/_269.java b/src/main/java/com/fishercoder/solutions/firstthousand/_269.java
@@ -9,20 +9,21 @@
 
 public class _269 {
     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, Integer> degree = new HashMap<>();
-            String result = "";
+            Map<Character, Set<Character>> charToSmallerCharsMap = new HashMap<>();//this map means all chars in the value set are after the char in the key
+            Map<Character, Integer> indegreeMap = new HashMap<>();//this map means how many chars are before this given char
+            StringBuilder result = new StringBuilder();
             if (words == null || words.length == 0) {
-                return result;
+                return result.toString();
             }
             for (String s : words) {
                 for (char c : s.toCharArray()) {
-                    degree.put(c, 0);
+                    //we go through each word, nothing to compare, so each char's degree should be zero
+                    //only when we compare words[i] with words[i+1], we know the order of different chars
+                    indegreeMap.put(c, 0);
                 }
             }
             for (int i = 0; i < words.length - 1; i++) {
@@ -31,46 +32,45 @@ public String alienOrder(String[] words) {
                 if (curr.length() > next.length() && curr.startsWith(next)) {
                     return "";
                 }
-                int minLen = Math.min(curr.length(), next.length());
-                for (int j = 0; j < minLen; j++) {
+                for (int j = 0; j < curr.length(); j++) {
                     char c1 = curr.charAt(j);
                     char c2 = next.charAt(j);
                     if (c1 != c2) {
-                        Set<Character> set = new HashSet<>();
-                        if (map.containsKey(c1)) {
-                            set = map.get(c1);
-                        }
+                        Set<Character> set = charToSmallerCharsMap.getOrDefault(c1, new HashSet<>());
                         if (!set.contains(c2)) {
                             set.add(c2);
-                            map.put(c1, set);
-                            degree.put(c2, degree.get(c2) + 1);
+                            charToSmallerCharsMap.put(c1, set);
+                            indegreeMap.put(c2, indegreeMap.get(c2) + 1);
                         }
+                        //no longer need to continue iterating through either one of these two words and should not to,
+                        //because the first two chars at the same position of these two words that differ decides the order
                         break;
                     }
                 }
             }
             Queue<Character> queue = new LinkedList<>();
-            for (char c : degree.keySet()) {
-                if (degree.get(c) == 0) {
+            for (char c : indegreeMap.keySet()) {
+                if (indegreeMap.get(c) == 0) {
+                    //this means no chars come before this char, so they should be at the head of this alien dictionary
                     queue.offer(c);
                 }
             }
             while (!queue.isEmpty()) {
                 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) {
+                result.append(curr);
+                if (charToSmallerCharsMap.containsKey(curr)) {
+                    for (char c : charToSmallerCharsMap.get(curr)) {
+                        indegreeMap.put(c, indegreeMap.get(c) - 1);
+                        if (indegreeMap.get(c) == 0) {
                             queue.offer(c);
                         }
                     }
                 }
             }
-            if (result.length() != degree.size()) {
+            if (result.length() != indegreeMap.size()) {
                 return "";
             }
-            return result;
+            return result.toString();
         }
     }
 

Original file line number	Diff line number	Diff line change
`@@ -9,20 +9,21 @@`
`9`	`9`
`10`	`10`	`public class _269 {`
`11`	`11`	`public static class Solution1 {`
`12`		`-`
`13`	`12`	`/**`
`14`	`13`	`* reference: https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs`
`15`	`14`	`*/`
`16`	`15`	`public String alienOrder(String[] words) {`
`17`		`- Map<Character, Set<Character>> map = new HashMap<>();`
`18`		`- Map<Character, Integer> degree = new HashMap<>();`
`19`		`- String result = "";`
	`16`	`+ Map<Character, Set<Character>> charToSmallerCharsMap = new HashMap<>();//this map means all chars in the value set are after the char in the key`
	`17`	`+ Map<Character, Integer> indegreeMap = new HashMap<>();//this map means how many chars are before this given char`
	`18`	`+ StringBuilder result = new StringBuilder();`
`20`	`19`	`if (words == null \|\| words.length == 0) {`
`21`		`- return result;`
	`20`	`+ return result.toString();`
`22`	`21`	`}`
`23`	`22`	`for (String s : words) {`
`24`	`23`	`for (char c : s.toCharArray()) {`
`25`		`- degree.put(c, 0);`
	`24`	`+ //we go through each word, nothing to compare, so each char's degree should be zero`
	`25`	`+ //only when we compare words[i] with words[i+1], we know the order of different chars`
	`26`	`+ indegreeMap.put(c, 0);`
`26`	`27`	`}`
`27`	`28`	`}`
`28`	`29`	`for (int i = 0; i < words.length - 1; i++) {`
`@@ -31,46 +32,45 @@ public String alienOrder(String[] words) {`
`31`	`32`	`if (curr.length() > next.length() && curr.startsWith(next)) {`
`32`	`33`	`return "";`
`33`	`34`	`}`
`34`		`- int minLen = Math.min(curr.length(), next.length());`
`35`		`- for (int j = 0; j < minLen; j++) {`
	`35`	`+ for (int j = 0; j < curr.length(); j++) {`
`36`	`36`	`char c1 = curr.charAt(j);`
`37`	`37`	`char c2 = next.charAt(j);`
`38`	`38`	`if (c1 != c2) {`
`39`		`- Set<Character> set = new HashSet<>();`
`40`		`- if (map.containsKey(c1)) {`
`41`		`- set = map.get(c1);`
`42`		`- }`
	`39`	`+ Set<Character> set = charToSmallerCharsMap.getOrDefault(c1, new HashSet<>());`
`43`	`40`	`if (!set.contains(c2)) {`
`44`	`41`	`set.add(c2);`
`45`		`- map.put(c1, set);`
`46`		`- degree.put(c2, degree.get(c2) + 1);`
	`42`	`+ charToSmallerCharsMap.put(c1, set);`
	`43`	`+ indegreeMap.put(c2, indegreeMap.get(c2) + 1);`
`47`	`44`	`}`
	`45`	`+ //no longer need to continue iterating through either one of these two words and should not to,`
	`46`	`+ //because the first two chars at the same position of these two words that differ decides the order`
`48`	`47`	`break;`
`49`	`48`	`}`
`50`	`49`	`}`
`51`	`50`	`}`
`52`	`51`	`Queue<Character> queue = new LinkedList<>();`
`53`		`- for (char c : degree.keySet()) {`
`54`		`- if (degree.get(c) == 0) {`
	`52`	`+ for (char c : indegreeMap.keySet()) {`
	`53`	`+ if (indegreeMap.get(c) == 0) {`
	`54`	`+ //this means no chars come before this char, so they should be at the head of this alien dictionary`
`55`	`55`	`queue.offer(c);`
`56`	`56`	`}`
`57`	`57`	`}`
`58`	`58`	`while (!queue.isEmpty()) {`
`59`	`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) {`
	`60`	`+ result.append(curr);`
	`61`	`+ if (charToSmallerCharsMap.containsKey(curr)) {`
	`62`	`+ for (char c : charToSmallerCharsMap.get(curr)) {`
	`63`	`+ indegreeMap.put(c, indegreeMap.get(c) - 1);`
	`64`	`+ if (indegreeMap.get(c) == 0) {`
`65`	`65`	`queue.offer(c);`
`66`	`66`	`}`
`67`	`67`	`}`
`68`	`68`	`}`
`69`	`69`	`}`
`70`		`- if (result.length() != degree.size()) {`
	`70`	`+ if (result.length() != indegreeMap.size()) {`
`71`	`71`	`return "";`
`72`	`72`	`}`
`73`		`- return result;`
	`73`	`+ return result.toString();`
`74`	`74`	`}`
`75`	`75`	`}`
`76`	`76`