Hash Table
This idea uses a hash table to record the times of appearances of each letter in the two stringss and t. For each letter in s, it increases the counter by 1 while for each letter in t, it decreases the counter by 1. Finally, all the counters will be 0 if they two are anagrams of each other.
The first implementation uses the built-in unordered_map and takes 36 ms.
1 class Solution { 2 public: 3 bool isAnagram(string s, string t) { 4 if (s.length() != t.length()) return false; 5 int n = s.length(); 6 unordered_map<char, int> counts; 7 for (int i = 0; i < n; i++) { 8 counts[s[i]]++; 9 counts[t[i]]--; 10 } 11 for (auto count : counts) 12 if (count.second) return false; 13 return true; 14 } 15 };
Since the problem statement says that "the string contains only lowercase alphabets", we can simply use an array to simulate the unordered_map and speed up the code. The following implementation takes 12 ms.
1 class Solution { 2 public: 3 bool isAnagram(string s, string t) { 4 if (s.length() != t.length()) return false; 5 int n = s.length(); 6 int counts[26] = {0}; 7 for (int i = 0; i < n; i++) { 8 counts[s[i] - 'a']++; 9 counts[t[i] - 'a']--; 10 } 11 for (int i = 0; i < 26; i++) 12 if (counts[i]) return false; 13 return true; 14 } 15 };
Sorting
For two anagrams, once they are sorted in a fixed order, they will become the same. This code is much shorter (this idea can be done in just 1 line using Python as here). However, it takes much longer time --- 76 ms in C++.
1 class Solution { 2 public: 3 bool isAnagram(string s, string t) { 4 sort(s.begin(), s.end()); 5 sort(t.begin(), t.end()); 6 return s == t; 7 } 8 };
