Last Updated on 2023-12-16 by Clay
Problem
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 * 104
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
The problem is to compare the character numbers of s
and t
are the same. You can also think we need them are the same string after sorting.
If you value space, you can sort the strings and compare then; The time complexity is O(n*log(n)) and space complexity is O(1).
If you value speed, you can use array or map. Use array is faster, but do not complete the "Follow up". The time complexity and space complexity is O(n).
C++ Sample Code
class Solution {
public:
bool isAnagram(string s, string t) {
// Base case
if (s.size() != t.size()) {
return false;
}
// Init
unordered_map<char, int> sMap;
unordered_map<char, int> tMap;
// Count
for (int i=0; i<s.size(); ++i) {
++sMap[s[i]];
++tMap[t[i]];
}
return sMap == tMap;
}
};
Python Sample Code
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Base case
if len(s) != len(t):
return False
# Init
sMap = {};
tMap = {};
# Count
for i in range(len(s)):
sMap[s[i]] = sMap.get(s[i], 0) + 1
tMap[t[i]] = tMap.get(t[i], 0) + 1
return sMap == tMap
But in Python case, use the built-in Counter
may be the better method. You just need to return Counter(s) == Counter(t)
.