[Leetcode][242. Valid Anagram] 3 Solutions: HashMap, Counting and Sorting, while Counting is the Fastest

By Long Luo

This article is the solution of Problem 242. Valid Anagram.

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

HashMap

t\textit{t} is an anagram of s\textit{s} which means that the characters in both strings appear in the same kind and number of times.

We can use two HashMap\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)O(n)
  • Space Complexity: O(S)O(S), S=26S = 26.

Counting

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

Traverse the frequency of the characters in the record string s\textit{s}, minus table\textit{table} the corresponding frequency in table\textit{table}, if table[i]<0\textit{table}[i] < 0, it means that t\textit{t} contains an extra character that is not in s\textit{s}, just return false\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)O(n)
  • Space Complexity: O(S)O(S), S=26S = 26.

Sorting

t\textit{t} is an anagram of s\textit{s} is equal to “two strings sorted equal”. Therefore, we can sort the strings s\textit{s} and t\textit{t} first, and 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)O(n \log n), sorting needs O(nlogn)O(n \log n), comparing two arrays need O(n)O(n), so total is O(nlogn)O(n \log n).
  • Space Complexity: O(logn)O(\log n), because sorting needs O(logn)O(\log n) space.

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