add a solution for 49

fishercoder1534 · fishercoder1534 · commit f64721ea4191 · 2021-10-14T12:13:53.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_49.java b/src/main/java/com/fishercoder/solutions/_49.java
@@ -9,6 +9,9 @@
 public class _49 {
 
     public static class Solution1 {
+        /**
+         * Time: O(n*k*logk) where n is the # of strings in the given input and k is the maximum length of each string
+         */
         public List<List<String>> groupAnagrams(String[] strs) {
             Map<String, List<String>> map = new HashMap<>();
             for (String word : strs) {
@@ -23,4 +26,30 @@ public List<List<String>> groupAnagrams(String[] strs) {
             return new ArrayList<>(map.values());
         }
     }
+
+    public static class Solution2 {
+        /**
+         * This is an improvement to the above solution in terms of time complexity.
+         * Time: O(n*k) where n is the # of strings in the given input and k is the maximum length of each string
+         */
+        public List<List<String>> groupAnagrams(String[] strs) {
+            Map<String, List<String>> map = new HashMap<>();
+            for (String word : strs) {
+                int[] count = new int[26];
+                for (char c : word.toCharArray()) {
+                    count[c - 'a']++;
+                }
+                StringBuilder sb = new StringBuilder();
+                for (int c : count) {
+                    sb.append(c);
+                    sb.append("$");
+                }
+                if (!map.containsKey(sb.toString())) {
+                    map.put(sb.toString(), new ArrayList<>());
+                }
+                map.get(sb.toString()).add(word);
+            }
+            return new ArrayList<>(map.values());
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_49Test.java b/src/test/java/com/fishercoder/_49Test.java
@@ -12,6 +12,7 @@
 
 import static junit.framework.TestCase.assertEquals;
 import static junit.framework.TestCase.assertTrue;
+import static org.assertj.core.api.Assertions.assertThat;
 
 public class _49Test {
     private static _49.Solution1 solution1;
