LeetCode Meditations: Valid Anagram
For this one, let's start with the description:
Given two strings
sandt, returntrueiftis an anagram ofs, andfalseotherwise.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.
And, both arguments will consist of lowercase English letters.
For example:
isAnagram('anagram', 'nagaram');
// -> true
isAnagram('rat', 'car');
// -> false
isAnagram('anagram', 'nagaram');
// -> true
isAnagram('rat', 'car');
// -> false
Here, we can use Map to store the letter counts in both strings. If the same letter in the second string doesn't occur the same number of times as in the first string, we know that they are not anagrams.
Of course, the first thing to check is if the lengths of the strings are equal, because if they are not, then there is no way they are anagrams in the first place.
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false;
}
let isValid = true;
let sDict = new Map();
let tDict = new Map();
// Initialize the objects with letters mapping to letter counts
for (const letter of s) {
const letterCount = sDict.get(letter);
!letterCount ? sDict.set(letter, 1) : sDict.set(letter, letterCount + 1);
}
for (const letter of t) {
const letterCount = tDict.get(letter);
!letterCount ? tDict.set(letter, 1) : tDict.set(letter, letterCount + 1);
}
// Check if a letter doesn't occur the same number of times
sDict.forEach((letterCount, letter) => {
if (tDict.get(letter) !== letterCount) {
isValid = false;
}
});
return isValid;
};
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false;
}
let isValid = true;
let sDict = new Map();
let tDict = new Map();
// Initialize the objects with letters mapping to letter counts
for (const letter of s) {
const letterCount = sDict.get(letter);
!letterCount ? sDict.set(letter, 1) : sDict.set(letter, letterCount + 1);
}
for (const letter of t) {
const letterCount = tDict.get(letter);
!letterCount ? tDict.set(letter, 1) : tDict.set(letter, letterCount + 1);
}
// Check if a letter doesn't occur the same number of times
sDict.forEach((letterCount, letter) => {
if (tDict.get(letter) !== letterCount) {
isValid = false;
}
});
return isValid;
};
Time and space complexity
My guess for the time complexity is as we iterate through the string's length to create the map. Space complexity would be as well, because creating the map grows linearly as the length of the string increases.
Using Python
Many things are potential one-liners in Python, so
collections.Counter(s) == collections.Counter(t)
collections.Counter(s) == collections.Counter(t)
is the easiest thing to do.
But to recreate the above code, it might look like this:
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
s_dict = {}
t_dict = {}
for letter in s:
s_dict[letter] = s_dict.get(letter, 0) + 1
for letter in t:
t_dict[letter] = t_dict.get(letter, 0) + 1
for letter, letter_count in s_dict.items():
if t_dict.get(letter, 0) != letter_count:
return False
return True
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
s_dict = {}
t_dict = {}
for letter in s:
s_dict[letter] = s_dict.get(letter, 0) + 1
for letter in t:
t_dict[letter] = t_dict.get(letter, 0) + 1
for letter, letter_count in s_dict.items():
if t_dict.get(letter, 0) != letter_count:
return False
return True
Note that we don't need an isValid flag in this case, as we're not checking the letter counts inside a function with limited scope inside some function like a forEach.
Also inside the last loop, as the letter in s_dict may not be in t_dict, we're using t_dict.get(letter, 0), so if it doesn't exist, it would be initialized with the count 0.
I don't think that's a good solution at all, though.
So let's take a deep breath, and look at NeetCode's solution.
NeetCode's solution was pretty similar to the Python version above.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
countS, countT = {}, {}
for i in range(len(s)):
countS[s[i]] = 1 + countS.get(s[i], 0)
countT[t[i]] = 1 + countT.get(t[i], 0)
for c in countS:
if countS[c] != countT.get(c, 0):
return False
return True
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
countS, countT = {}, {}
for i in range(len(s)):
countS[s[i]] = 1 + countS.get(s[i], 0)
countT[t[i]] = 1 + countT.get(t[i], 0)
for c in countS:
if countS[c] != countT.get(c, 0):
return False
return True
The time and space complexity in this case are as well.
To get rid of the extra memory usage and make the space complexity , he mentions the solution where you can compare the sorted versions of the strings:
sorted(s) == sorted(t)
sorted(s) == sorted(t)
In the case of TypeScript (or JavaScript) it could be:
[...s].sort().join('') === [...t].sort().join('');
[...s].sort().join('') === [...t].sort().join('');
But, of course, sorting algorithms can't get better than when it comes to time complexity, and some of them use space to create additional storage as well, so it's another trade-off.
We can take one more deep breath now.
Next up is Two Sum, until then, happy coding.