I started a series on JavaScript solutions to common algorithms and javascript problems. In case you missed the first one, here's a link to it. Ear...
For further actions, you may consider blocking this person and/or reporting abuse
It's Python (so, off-topic), but I couldn't help myself:
O(n), if you're wondering.
Flawed, would fail for strings like ('aabb', 'aaab')
Good catch. I'd overlooked that edge case. Let me ponder....
AHA! The most obvious solution is...
sorted()
employs Timsort, which has a worst case ofO(n log n)
. Everything else is still onlyO(n)
.Naturally, I'm sure there's a more efficient solution if I chew on this longer, but that'd be the one I'd probably use in production; reasonable performance, readable, maintainable, etc.
EVEN BETTER! I just thought of a completely
O(n)
solution that relies on the commutative property of addition, and the fact that any letter would have a unique numeric equivalent (retrieved viaord()
).Ahhh, I love a good hack.
Nope, this is flawed too. There are multiple ways to express a sum. 3+2=5 and 4+1=5 as well.
So ord('a') + ord('z') = ord('b') + ord('y')
Would fail for strings such as ('az', 'by').
Hmm, hadn't considered that angle....
Prime factorizations are unique so if you map each letter to a prime and then take the product of those primes, you'd have a unique representation of the characters in the word. See this classic tweet for a better explanation.
Not very efficient or fast, however.
I mean its time complexity is
O(n)
-ish but yeah the large number multiplication would get you for longer words.26th prime is 101 so I imagine zzzzzzzzzzzzz et all would take more time
It's not efficient, but I wonder if a Cantor pairing of the
ord()
values would work. It would certainly be optimal if all the strings were two letters. The trouble is, those numbers get very big, very fast.What do you think?
Copyright (c) 2019 Caleb Pitan
😇😁😁
I think that function expressions using ! are there just to make the code less readable.
My bad! I won't lie to you I really don't know the use of the "!", but I think it's to indicate an
iife
inside the function, hence aid readability. I put it because in my early years I saw a lot of these around, and I thought having it around or not affects nothing. Didn't know it affects readability, although I don't understand how. I wouldn't mind if you told me.I prefer explicit to implicit (comes from enjoying Python too much...) and
!(function(){...}();
is just... well, if you haven't seen it before you have no idea what the gosh darnit is going on.digitalfortress.tech/js/exclamatio...
I initially thought about that approach, but discarded it for an obvious reason:
Smart 😃.
It's just too obvious. Didn't take time to analyze it. It struck my mind as I saw this post and I put it down.
I thought about using \W instead of ^w as you wrote)
There's really no difference, it's just left to choice.
Know it. But I think this way is more elegant and perfomance
Solution 1 might not be completely correct if you don't check that the length of s and t are the same otherwise return false like so:
Otherwise this test will return true even though it should be false
My first solution (ES2019) looks like this:
Here's an O(∞) solution inspired by bogosort. If it halts,
a
andb
are anagrams.My intuition, before i saw any of the solutions, went into the 2nd one because it feels like it would be the easiest to understand and the fastest. I wonder if thats the case ;)
Thank you for the brain teaser, good beginning of the day :)
In order to remove spaces, you are calling string.replace once for every occurrence of " " (space) in each string. An easier way to remove whitespace in a string is to use a regular expression object with a global modifier, which will replace all matching characters in the string. Then, you can get rid of your while-loops, and your code becomes slightly easier to read. I hope it will help you to complete your Anagram checker project .
You can also use the /\s/g regular expression object to replace all whitespace including tabs, newlines, etc.
const same = (s1, s2) => { const str1 = s1.toLowerCase(); const str2 = s2.toLowerCase(); if (str1 === str2) return true; if (str1.length !== str2.length) return false; const obj1 = {}; const obj2 = {}; str1.split('').forEach((s, i) => { obj1[str1[i]] = (obj1[str1[i]] || 0) + 1; obj2[str2[i]] = (obj2[str2[i]] || 0) + 1; }); const arr1 = Object.entries(obj1).map(String).sort().toString(); const arr2 = Object.entries(obj2).map(String).sort().toString(); return arr1 === arr2; }; same('textwisttime', 'timewisttext');
tried all the above and the below solutions but the least execution time was taken by this one.
Great article Sarah! Mind sharing any resources for leveling up on Data Structures and Algorithms. Thanks
I'm taking a course by Stephen Grider on Udemy. Another recommended course is by Colt Steele - JavaScript Algorithms and Data Structures Masterclass.
This is a favorite interview question of mine. The character map solution is what most people seem to do - myself included!
Solution 2 is not correct. What if I pass a word with extra letters to string 2???
For example?