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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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.

1
2
3
4
5
6
7
8
9
10
11

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}\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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. 😉😃💗