sorted() employs Timsort, which has a worst case of O(n log n). Everything else is still only O(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 via ord()).
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.
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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.