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 = "listen", t = "silent"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Example 3:
Input: s = "hello", t = "world"
Output: false
Solution
We can solve this problem by calculating how many times each character appears in both the strings. If the frequency of each character is the same in both the given strings, we can conclude that the strings are anagrams of each other.
We can use a hash map to store the frequency of each character in both strings.
For each character in the string, the frequency of that character in string s
is incremented and the frequency of that character in string t
is decremented. After iterating over all characters in the strings, we will check if the frequency of all characters is 0. If it is, the strings are anagrams of each other and the function returns true. Otherwise, it returns false.
Code
Here is the code for this algorithm:
Time Complexity
The time complexity of this algorithm is O(n), where n is the length of the strings. This is because the algorithm iterates over each character in the strings once and performs a constant amount of work for each character.
Space Complexity
The space complexity of this algorithm is O(1), as the size of the hash map is proportional to the number of unique characters in the strings. In the worst case, all characters in the strings are unique, so the size of the hash map would be 26 (the number of letters in the alphabet).
However, in most cases, the number of unique characters is much smaller than 26, so the space complexity is closer to O(k), where k is the number of unique characters in the strings.