Hey everyone! Welcome back to Code Review, a series of coding interview challenges and career related content released weekly exclusively on Dev.to...
For further actions, you may consider blocking this person and/or reporting abuse
Hello!
How to check that two words are anagrams?
Should we
If I was on the hiring side, I am not sure I would have choosen a candidate who opt for the second solution and waste its time on algorithm trivia.
Have a look at this snippet and run it from pl.kotl.in/swFfcgRPy
As you can see, your first intuition was right.
Sorting an array is a bulletproof way to check that two words are an anagram.
Now if we are talking about the price of things, the first solution is the optimal one.
Words are usually very small lists. Even German words.
Let's assume I have alien words of 1 million characters.
That still takes less close to no time at all to sort out.
Who cares? Not the business.
On the other hand, a smart business does not particularly like developers who reinvent wheels.
Such a developer will spend much more than one second reinventing an algorithm for this.
It might be buggy, which means that the business will have to go through the complete lifecycle of having a client report a bug, file a jira ticket, wait that someone is ready, fix it, do a release, announce it.
It's important to udnerstand that your time isn't free and is, in fact, quite expansive.
So a smart business should in my opinion gives it thumbs up to a candidate that use the
.sort()
function from the standard library.Good effort, but unfortunately this solution doesn't always work.
E.g. when
str1
isaaaaa
andstr2
isabbbb
, it returnstrue
when it should be false.It's because
.includes
checks that the letter is anywhere in the string, not caring about how many times. However the number of times the letter appears also needs to match the other string.aaaaa
andabbbb
is not an anagram in the first place, is it?That's right. That's what we're testing for: whether they are anagrams of each other. So in the
str1 = aaaaa
andstr2 = abbbb
case it should returnfalse
because as you say they're not anagrams of each other.function anagram(str1, str2) {
return (
str1.length == str2.length &&
str1.split("").every(c => str2.includes(c)) &&
str2.split("").every(c => str1.includes(c))
);
}
... and its still about 70% faster.
Nice :)
The new method returns
true
for"abb", "aab"
, I don't think it should.You're right,
every
just won't work. My method works for a few cases but not all.So with the sort function you have
O(nlog(n))
. Then how about this solution forO(n)
. You have a dictionary with the char as key, and counter (how many times char appeared) as value. You iterate with a for over both arrays at the same time(O(n))
and each char in the first string adds to that key, while the same char in the second string subtracts. In the end you want to have 0 for all keys:or stuff each string into a hashmap (python duct, js object) that maps each letter to a count of occurrences. then compare values and keys. both are linear operations, thus more optimal than sorting.
maps tend to be the more optimal solution to βfinding things in arrays using nested loopsβ than sorting.
sorting is more useful when you have space constraints β eg you can sort in place and then compare without hashmaps β or want to do additional work than exact comparison β eg navigate a tree representation of words in incremental ways.
const isAnagram = (str1, str2) =>
[...str1].sort().join("") === [...str2].sort().join("");
speaking of free, you overlooked the alloc
That's a great solution. Thanks for sharing!