reducing complexity to linear complixity (TheAlgorithms#2087)

Itayventura · yanglbme · web-flow · commit a47546314659 · 2021-02-21T09:02:07.000+08:00
* reducing complexity to linear complixity

* reducing complexity to linear

* update CheckAnagrams algo

Co-authored-by: Yang Libin &lt;contact@yanglibin.info&gt;
diff --git a/strings/CheckAnagrams.java b/strings/CheckAnagrams.java
@@ -1,32 +1,52 @@
 package strings;
 
-import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
 
 /**
  * Two strings are anagrams if they are made of the same letters arranged differently (ignoring the
  * case).
  */
 public class CheckAnagrams {
-  public static void main(String[] args) {
-    assert isAnagrams("Silent", "Listen");
-    assert isAnagrams("This is a string", "Is this a string");
-    assert !isAnagrams("There", "Their");
-  }
+    public static void main(String[] args) {
+        assert isAnagrams("Silent", "Listen");
+        assert isAnagrams("This is a string", "Is this a string");
+        assert !isAnagrams("There", "Their");
+    }
 
-  /**
-   * Check if two strings are anagrams or not
-   *
-   * @param s1 the first string
-   * @param s2 the second string
-   * @return {@code true} if two string are anagrams, otherwise {@code false}
-   */
-  public static boolean isAnagrams(String s1, String s2) {
-    s1 = s1.toLowerCase();
-    s2 = s2.toLowerCase();
-    char[] values1 = s1.toCharArray();
-    char[] values2 = s2.toCharArray();
-    Arrays.sort(values1);
-    Arrays.sort(values2);
-    return new String(values1).equals(new String(values2));
-  }
+    /**
+     * Check if two strings are anagrams or not
+     *
+     * @param s1 the first string
+     * @param s2 the second string
+     * @return {@code true} if two string are anagrams, otherwise {@code false}
+     */
+    public static boolean isAnagrams(String s1, String s2) {
+        int l1 = s1.length();
+        int l2 = s2.length();
+        s1 = s1.toLowerCase();
+        s2 = s2.toLowerCase();
+        Map<Character, Integer> charAppearances = new HashMap<>();
+
+        for (int i = 0; i < l1; i++) {
+            char c = s1.charAt(i);
+            int numOfAppearances = charAppearances.getOrDefault(c, 0);
+            charAppearances.put(c, numOfAppearances + 1);
+        }
+
+        for (int i = 0; i < l2; i++) {
+            char c = s2.charAt(i);
+            if (!charAppearances.containsKey(c)) {
+                return false;
+            }
+            charAppearances.put(c, charAppearances.get(c) - 1);
+        }
+
+        for (int cnt : charAppearances.values()) {
+            if (cnt != 0) {
+                return false;
+            }
+        }
+        return true;
+    }
 }
