3 Approaches: HashMap, Sorting and Counting
Leetcode 242. Valid Anagram.\n\nBy Frank Luo\n\nHere shows 3 Approaches to slove this problem: HashMap, Sorting and Counting.\n\n\n# HashMap\n\n$\textit{t}$ is 
[Leetcode](https://leetcode.com/) [242. Valid Anagram](https://leetcode.com/problems/valid-anagram).\n\n***By Frank Luo***\n\nHere shows **3** Approaches to slove this problem: **HashMap**, **Sorting** and **Counting**.\n\n\n# HashMap\n\n$\\textit{t}$ is an anagram of $\\textit{s}$ which means that the characters in both strings appear in the same kind and number of times.\n\nWe can use two $\\texttt{HashMap}$ to store the characters and the number of times, then compare the keys and values.\n\n```java\n    public boolean isAnagram(String s, String t) {\n        if (s.length() != t.length()) {\n            return false;\n        }\n\n        int len = s.length();\n\n        Map<Character, Integer> sMap = new HashMap<>();\n        Map<Character, Integer> tMap = new HashMap<>();\n\n        for (int i = 0; i < len; i++) {\n            sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);\n            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);\n        }\n\n        for (Map.Entry<Character, Integer> entry : sMap.entrySet()) {\n            char ch = entry.getKey();\n            int cnt = entry.getValue();\n            if (!tMap.containsKey(ch) || cnt != tMap.get(ch)) {\n                return false;\n            }\n        }\n\n        return true;\n    }\n```\n\n## Analysis\n\n- **Time Complexity**: $O(n)$\n- **Space Complexity**: $O(S)$, $S = 26$.\n\n\n# Sorting\n\n$\\textit{t}$ is an anagram of $\\textit{s}$ is equal to "two strings sorted equal". Therefore, we can sort the strings $\\textit{s}$ and $\\textit{t}$ first, then check whether the sorted strings are equal.\n\n```java\n    public static boolean isAnagram_sort(String s, String t) {\n        if (s.length() != t.length()) {\n            return false;\n        }\n\n        char[] sArr = s.toCharArray();\n        char[] tArr = t.toCharArray();\n        Arrays.sort(sArr);\n        Arrays.sort(tArr);\n        return Arrays.equals(sArr, tArr);\n    }\n```\n\n## Analysis\n\n- **Time Complexity**: $O(nlogn)$, sorting needs $O(nlogn)$, comparing two arrays need $O(n)$, so total is $O(nlogn)$.\n- **Space Complexity**: $O(logn)$, because sorting needs $O(logn)$ space.\n\n# Counting\n\nSince the string contains only $26$ lowercase letters, we can maintain a frequency array $\\textit{table}$ of length $26$. \n\nTraverse the frequency of the characters in the record string $\\textit{s}$, minus $\\textit{table}$ the corresponding frequency in $\\textit{table}$, if $\\textit{table}[i] \\lt 0$, it means that $\\textit{t}$ contains an extra character that is not in $\\textit{s}$, just return $\\textit{false}$.\n\n```java\n    public boolean isAnagram_cnt(String s, String t) {\n        if (s.length() != t.length()) {\n            return false;\n        }\n\n        int len = s.length();\n        int[] cnt = new int[26];\n        for (int i = 0; i < len; i++) {\n            cnt[s.charAt(i) - \'a\']++;\n            cnt[t.charAt(i) - \'a\']--;\n        }\n\n        for (int i = 0; i < 26; i++) {\n            if (cnt[i] < 0) {\n                return false;\n            }\n        }\n\n        return true;\n    }\n```\n\n## Analysis\n\n- **Time Complexity**: $O(n)$\n- **Space Complexity**: $O(S)$, $S = 26$.\n\n\n--------------------------\n\nAll suggestions are welcome. \nIf you have any query or suggestion please comment below.\nPlease upvote\uD83D\uDC4D if you like\uD83D\uDC97 it. Thank you:-)\n\nExplore More [Leetcode Solutions](https://leetcode.com/discuss/general-discussion/1868912/My-Leetcode-Solutions-All-In-One). \uD83D\uDE09\uD83D\uDE03\uD83D\uDC97\n\n
['Array', 'String', 'Sorting', 'Counting', 'Java']