Problem statement
Given two strings s
and t
, return true
if t
is an anagram of s
, and false
otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1
Input: s = "anagram", t = "nagaram"
Output: true
Example 2
Input: s = "rat", t = "car"
Output: false
Constraints
1 <= s.length, t.length <= 5 * 10^4
.s
andt
consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Solution 1: Rearrange both s
and t
into a sorted string
Code
#include <iostream>
#include <algorithm>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
int main() {
cout << isAnagram("anagram", "nagaram") << endl;
cout << isAnagram("rat", "car") << endl;
}
Output:
1
0
Complexity
Runtime:
O(NlogN)
, whereN = s.length
.Extra space:
O(1)
.
Solution 2: Count the appearances of each letter
Code
#include <iostream>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
int alphabet[26];
for (int i = 0; i < 26; i++) {
alphabet[i] = 0;
}
for (char& c : s) {
alphabet[c - 'a']++;
}
for (char& c : t) {
alphabet[c - 'a']--;
if (alphabet[c - 'a'] < 0) {
return false;
}
}
return true;
}
int main() {
cout << isAnagram("anagram", "nagaram") << endl;
cout << isAnagram("rat", "car") << endl;
}
Output:
1
0
Complexity
Runtime:
O(N)
, whereN = s.length
.Extra space:
O(1)
.
Solution 3: If the inputs contain Unicode characters
In the solutions above, the array alphabet
represents 26 letters 'a'
to 'z'
. You can generalize to allow it contains any character by using a map.
Code
#include <iostream>
#include <unordered_map>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
unordered_map<char, int> alphabet;
for (char& c : s) {
alphabet[c]++;
}
for (char& c : t) {
alphabet[c]--;
if (alphabet[c] < 0) {
return false;
}
}
return true;
}
int main() {
cout << isAnagram("anagæam", "nagaæam") << endl;
cout << isAnagram("rat", "car") << endl;
}
Output:
1
0
Complexity
Runtime:
O(N)
, whereN = s.length
.Extra space:
O(1)
.
Key takeaway
An array of 26 integers can represent the English alphabet.
Counting the appearances can help identify if a word is a permutation of another.
You can use a map to count the appearances of the letters of a word.
Thanks for reading. Feel free to share your thought about my content.
What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.