The 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
Solution
We know that the two strings are anagrams if:
- They have the same length
- They have the same characters and the same quantity of each character
So, if we can verify that the strings pass these two criteria, we can verify that they are valid anagrams.
We can check if they are the same length by simply using len
:
len(s) == len(t) # boolean expression
But how can we check if they have the same characters and the same quantity of each character? We can use hash maps. For each string, we can create a hash map that includes every unique character in the string and its frequency in the string.
For example, this would be the hash map of the string s
, which has a value of "anagram"
:
s = "anagram" countS = {"a": 3, "n": 1, "g": 1, "m": 1}
Once, we have created the hash maps, we can check if they are equivalent by using a boolean expression:
countS == countT
So, let’s put it all together. These are all the steps we have to take:
- We check if the strings are not the same length. If they’re not, we can immediately return False without doing any other code.
- We create empty hash maps for the two strings
s
andt
. - We loop through each character in s and t and add them to the hash maps. If the character does not exist in the hash map, a new key for the character is added and the value is initialized to 0 (then we add 1). If a key for the character does exist in the hash map, we add 1 to the value.
- We check if the two hash maps are equivalent. If they are, we return True. If they are not, we return False.
This is the final code.
def isAnagram(self, s: str, t: str) -> bool: # Step 1: check if same length if len(s) != len(t): return False # Step 2: create hash maps countS = {} countT = {} # Step 3: loop through characters to add to hash map for i in range(len(s)): countS[s[i]] = 1 + countS.get(s[i], 0) countT[t[i]] = 1 + countT.get(t[i], 0) # Step 4: check if hash maps are equivalent if (countS == countT): return True else: return False
This solution has a time complexity of O(s + t) or simply O(n) because we have to iterate through each of the strings. The space complexity is also O(s + t) because we are building hash maps that are the sizes of arrays s and t.
There is another solution that is much more simple, but less efficient. We can sort both of the strings and see if the sorted versions are equivalent. This works because, if they are anagrams, then they will have the same sorted value.
def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t)
A good sorting algorithm can sort an array of characters in O(n * log(n)) time. The space complexity could be either O(1) or O(n)