[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.

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