[LeetCode][242. Valid Anagram] 3 Approaches: HashMap, Sorting and Counting

By Long Luo

This article is the solution 3 Approaches: HashMap, Sorting and Counting of Problem 242. Valid Anagram.

Here shows 3 Approaches to slove this problem: HashMap, Sorting and Counting.

HashMap

$\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.

We can use two $\texttt{HashMap}$ to store the characters and the number of times, then compare the keys and values.

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int len = s.length();

    Map<Character, Integer> sMap = new HashMap<>();
    Map<Character, Integer> tMap = new HashMap<>();

    for (int i = 0; i < len; i++) {
        sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
        tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
    }

    for (Map.Entry<Character, Integer> entry : sMap.entrySet()) {
        char ch = entry.getKey();
        int cnt = entry.getValue();
        if (!tMap.containsKey(ch) || cnt != tMap.get(ch)) {
            return false;
        }
    }

    return true;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(S)$, $S = 26$.

Sorting

$\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.

public static boolean isAnagram_sort(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    char[] sArr = s.toCharArray();
    char[] tArr = t.toCharArray();
    Arrays.sort(sArr);
    Arrays.sort(tArr);
    return Arrays.equals(sArr, tArr);
}

Analysis

• Time Complexity: $O(nlogn)$, sorting needs $O(nlogn)$, comparing two arrays need $O(n)$, so total is $O(nlogn)$.
• Space Complexity: $O(logn)$, because sorting needs $O(logn)$ space.

Counting

Since the string contains only $26$ lowercase letters, we can maintain a frequency array $\textit{table}$ of length $26$.

Traverse 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}$.

public boolean isAnagram_cnt(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int len = s.length();
    int[] cnt = new int[26];
    for (int i = 0; i < len; i++) {
        cnt[s.charAt(i) - 'a']++;
        cnt[t.charAt(i) - 'a']--;
    }

    for (int i = 0; i < 26; i++) {
        if (cnt[i] < 0) {
            return false;
        }
    }

    return true;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(S)$, $S = 26$.

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗