Given two strings s
and t
, return true
if t
is an anagram of s
, and false
otherwise.
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
and t
consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
This problem asks whether two strings, s
and t
, are anagrams of each other. An anagram is a word or phrase formed by rearranging the letters of another word or phrase. This means that s
and t
must have the same length, and each character in s
must have a corresponding character in t
with the same frequency.
We explore two main approaches: counting character frequencies and sorting.
This approach uses a hash table (or an array in this case since we only have lowercase English letters) to store the frequency of each character in string s
. Then, we iterate through string t
, decrementing the count for each character encountered. If at any point a count becomes negative, it means t
has more occurrences of a character than s
, and they are not anagrams. If after iterating through t
all counts are zero, s
and t
are anagrams.
Algorithm:
s
and t
are different, they cannot be anagrams; return false
.cnt
of size 26 (for lowercase English letters) and initialize all elements to 0.s
, incrementing the count for each character (cnt[s[i] - 'a']++
).t
, decrementing the count for each character (cnt[t[i] - 'a']--
).t
, iterate through cnt
. If any element is not 0, it means there's an unequal character frequency; return false
.true
.Time Complexity: O(n), where n is the length of the strings. We iterate through each string once. Space Complexity: O(1). We use a fixed-size array of size 26.
Code Examples:
(See the Python, Java, C++, Go, TypeScript, Rust, Javascript, C#, and C code examples provided in the original response. These all implement this approach efficiently).
This approach leverages the fact that anagrams have the same characters when sorted. We sort both strings and then compare them for equality.
Algorithm:
s
and t
alphabetically.true
; otherwise, return false
.Time Complexity: O(n log n), where n is the length of the strings, due to the sorting step.
Space Complexity: O(n) in some implementations due to the creation of new sorted strings (although in place sorting algorithms can lower this). However, in languages like C++ that use std::sort
, space complexity can be considered O(log n) due to recursive calls.
Code Examples (Illustrative):
(The Rust example from the original response utilizes this sorting approach. Note that this is less efficient than the counting approach for this specific problem).
Choosing the Best Approach:
For this specific problem, where the character set is limited to lowercase English letters, the counting character frequencies approach (Approach 1) is significantly more efficient due to its linear time complexity. The sorting approach becomes more competitive when dealing with larger character sets or when sorting is already a necessary operation within a broader context. In many cases, the improved time complexity of O(n) vs O(n log n) is preferred for improved efficiency.